DFSで塗り分けて矛盾が起きなければOK 二部グラフ判定をUnionFindTreeで行う - noshi91のメモ UnionFind 辺u,vについて「uが赤ならその時に限りvは青」のiff関係が成り立つのでUnionFindで充足判定ができる