Union-Find木を利用した無向グラフの閉路検出 - Qiita

本記事でしたいこと 下図のように無向グラフが与えられた時にその中に閉路があるかどうか判定します． (画像はgenerate DOTを利用し作成しました) 方法１ : DFS(深さ優先探索)で解く このようなルールで解けます． 今いるノードからつながっているノードへ移動する．ただし，一つ前にいたノードへは戻らない． 今いるノードに過去一度でも通っていたら閉路である． 閉路があると判定できなかったら閉路はない． DFSのソースコード vector<int> isPassed(101010, false); vector<vector<int>> graph(101010); // dfs(今いるノード, 一つ前にいたノード) bool dfs(const int current, const int before) { isPassed[current] = true; for(int i =