# yukicoder No.2277 Honest or Dishonest ?

## 問題

[yukicoder No.2277 Honest or Dishonest ?](https://yukicoder.me/problems/no/2277)

## 解説

2-SAT の解法と同様に考える．

$2N$ 頂点のグラフ $G$ を考える．$G$ に次のように辺を張る．
- $1\leq i\leq Q$ に対し $A_i,B_i+C_iN$ 間，$A_i+N,B_i+(1-C_i)N$ 間に無向辺を張る．

このときある $i\ (1\leq i\leq N)$ で $i,i+N$ が連結ならば正直・嘘つきの割り振りによらずそもそも条件が矛盾していることになるので答えは $0$．そうでない場合，連結成分の個数を $X$ として答えは $2^{X/2}$．

実装は Union-Find を使えば計算量 $O((N+Q)\alpha(N))$．