2部グラフの判定の練習：BFS・DFS・Union-Find - Qiita

2部グラフの判定をきちんとやったことが無かったので練習することにした。 また、通常のグラフ探索の方法で気になる点があり、Union-Findの要領で解決できそうだったので、これも試してみた。 グラフ探索 2部グラフの判定をするには、グラフの頂点に2値（例えば 0 と 1 ）を振ってみて、矛盾が生じるか調査する。「辺で繋がった2頂点は逆の値」という規則があるため、適当な頂点に値を決め打ちしたら隣接する頂点を貪欲に埋めていけばいい（探索順序は問わない）。隣接する頂点に既に値が振ってあれば、それが期待通りかどうか検査する。 1セットの探索（例えば下記コードの bfs() 1回の呼び出し）では開始地点と連結な頂点しか調べられないので、未調査の頂点を探して何セットか探索する。 幅優先探索（BFS） 開始地点から近い順に頂点を埋めていくパターン。 n, m = gets.split.map!(&:to