UnionFind

集合の併合と、共通の集合かどうかのチェックが高速なデータ構造。

グラフに辺を追加して、二頂点が連結かどうかのチェックが高速、という捉え方もできる。

N個の対象間の関係に関して、それがiffに分解できるならグラフの辺として記述できる

例えばグーチョキパーのいずれかである対象があったときに「xはyに勝つ」は、「xがグーである iff yがチョキである」のような3つのiffに分解できるので3Nの頂点集合に3本の辺を追加することに相当する

連結成分は条件を充足する解に相当する

iffでない場合→2-SAT