混乱した村人がいない場合、村人 \(i\) が村人 \(j\) を正直者であると証言したということは、村人 \(i\) と村人 \(j\) の属性（正直者 or 嘘つき）が同じであるということを意味します。嘘つきと証言した場合は、この逆です。したがって、正直者という証言の辺に重み \(0\) 、嘘つきという証言に重み \(1\) を割り当てたグラフが（重み付きの）二部グラフであるということと証言に矛盾が無いことが同値です。

村人 \(i\) が混乱していたとすると、村人 \(i\) の証言による辺の重みが反転することになります。ここで、以下のようなグラフを考えます。

• 村人自身を表す頂点 \(U_i\) と村人の証言を表す頂点 \(V_i\) の合計\(2N\) 頂点からなる
• \(V_{A_i}, U_{B_i}\) 間に重み \(C_i\) の辺を張る
• \(U_i, V_i\) 間に、村人 \(i\) が混乱していなければ重み \(0\) 、混乱していれば重み \(1\) の辺を張る

このとき、上記のグラフが二部グラフになるように、二番目の種類の辺を張ればよいです。したがって、ポテンシャル付き union-find などを用いれば、

• まず一番目の種類の辺を張る。この時点で二部グラフでなければ題意を満たす割り当ては存在しない
• 次に、好きな順番で二番目の種類の辺を、ポテンシャルの差と食い違わないような重みで張っていく（その時点で連結でなければ自由な重みで良い）

とすることで題意を満たす構築、またはそれが不可能であることの検知が可能です。

実装例：https://atcoder.jp/contests/arc188/submissions/60033237