yukicoder No.1640 簡単な色塗り - かんプリンの学習記録

公式解説とは別の解法です．
問題はこちら

問題概要
解説1：最大二部マッチング
解説2：2-SAT
提出プログラム
感想

問題概要

${1,2,\cdots,N}$ と番号付けされた ${N}$ 個の白い球がある．球 ${A_i}$ または球 ${B_i}$ を選んで黒く塗ることができるという操作を ${N}$ 回行う．すべての球を黒で塗ることが可能かどうかを判定し，可能なら塗り方を出力せよ．

${1\leq N\leq 10^5\\ 1\leq A_i,B_i\leq N}$

解説1：最大二部マッチング

${N}$ 個の頂点 ${U_i}$ と ${N}$ 個の頂点 ${V_i}$ を作り， ${U_i}$ と ${V_{A_i}}$ の間， ${U_i}$ と ${V_{B_i}}$ の間に辺を張る．このグラフの最大マッチングが答え．Dinicを用いると ${O(N\sqrt{N})}$ とかになるが間に合う．この方法だと ${3}$ つ以上の選択肢がある場合でも解ける．

解説2：2-SAT

${N}$ 個の論理変数 ${x_i}$ を考える． ${x_i}$ を ${A_i}$ を選ぶことに， ${\lnot{x_i}}$ を ${B_i}$ を選ぶことに対応させる． ${A_i=A_j}$ なら ${(\lnot{x_i}\lor\lnot{x_j})}$ ， ${A_i=B_j}$ なら ${(\lnot{x_i}\lor x_j)}$ ， ${B_i=B_j}$ なら ${(x_i\lor x_j)}$ という節を追加していけば2-SATを解くアルゴリズムで解ける．このままだと最悪 ${O(N^2)}$ になるが，ABC210 F - Coprime Solitaireと同じようにして節の数を省略することで ${O(N)}$ で解ける．

提出プログラム

https://yukicoder.me/submissions/687124 最大二部マッチング
https://yukicoder.me/submissions/687347 2-SAT

感想

2-SATの節削減覚えたので使ってみた．