閉路の検出
無向グラフ
閉路が存在するか自体はトポロジカルソートによって判別可能です。
有向グラフ
具体的な閉路のパスを1つ取得方法としては、DFSが挙げられます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
struct Edge { int to; Edge(int _to) : to(_to) { } }; using Graph = vector<vector<Edge>>; int cycle_node = -1; // 閉路上に存在するノードのid vb seen; // 探索済みフラグ vb finished; // 探索済みで、絶対にサイクルがないノード vi history; void dfs(const Graph& g, int idx) { if (finished[idx]) { return; } history.push_back(idx); // 探索終了していないけど訪問済みなノードに到達 if (seen[idx]) { // それは閉路である cycle_node = idx; return; } seen[idx] = true; for (const auto& e : g[idx]) { if (finished[e.to]) continue; dfs(g, e.to); if (cycle_node != -1) return; } finished[idx] = true; history.pop_back(); } // 閉路のパス // 戻り値: 0→閉路なし 1→閉路あり // cycle: 閉路のpath int find_cycle(const Graph& g, vector<int>& cycle) { ll n = g.size(); // init cycle_node = -1; seen.assign(n, false); finished.assign(n, false); cycle.clear(); // 全ての頂点を確認する rep(i, n) { dfs(g, i); // サイクルが見つかった時点でループを抜ける if (cycle_node != -1) { break; } } if (cycle_node == -1) { return 0; } // historyの始めにあるサイクルと無関係なデータを削除 cycle.push_back(cycle_node); for (auto it = history.rbegin() + 1; it != history.rend(); it++) { if (*it == cycle[0]) { break; } cycle.push_back(*it); } reverse(all(cycle)); return 1; } |
関連問題
- Pure (ABC142)