競プロノート

Appearance

サイクル検出（Cycle Detection） ​

グラフに閉路が存在するか判定し、必要に応じてサイクルを復元する。

特徴 ​

項目内容
用途閉路の存在判定・復元
対象有向・無向グラフ
計算量O(V+E)
空間計算量O(V+E)

考え方 ​

DFSで探索中の頂点に戻る辺があれば、サイクルが存在する。

有向グラフ ​

頂点の訪問状態を3種類に分ける。

  • 0：未訪問
  • 1：探索中
  • 2：探索完了

state[nv] == 1 ならサイクルが存在する。

単に訪問済みかどうかだけでは判定できない点に注意。

無向グラフ ​

親へ戻る逆辺を除外し、それ以外の探索中の頂点へ戻る辺があればサイクルが存在する。

多重辺がある場合は、親頂点ではなく親辺のIDで除外する。

実装 ​

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }

    vector<int> state(n), parent(n, -1), cycle;
    auto dfs = [&](auto&& self, int v) -> bool {
        state[v] = 1;
        for (int nv : g[v]) {
            if (state[nv] == 0) {
                parent[nv] = v;
                if (self(self, nv)) return true;
            } else if (state[nv] == 1) {
                cycle.push_back(nv);
                for (int u = v; u != nv; u = parent[u]) cycle.push_back(u);
                cycle.push_back(nv);
                reverse(cycle.begin(), cycle.end());
                return true;
            }
        }
        state[v] = 2;
        return false;
    };
    for (int v = 0; v < n; v++) {
        if (state[v] == 0 && dfs(dfs, v)) break;
    }

    if (cycle.empty()) cout << "No\n";
    else {
        cout << "Yes\n";
        for (int v : cycle) cout << v << ' ';
        cout << '\n';
    }
}
cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    vector<int> state(n), parent(n, -1), cycle;
    auto dfs = [&](auto&& self, int v, int pe) -> bool {
        state[v] = 1;
        for (auto [nv, id] : g[v]) {
            if (id == pe) continue;
            if (state[nv] == 0) {
                parent[nv] = v;
                if (self(self, nv, id)) return true;
            } else if (state[nv] == 1) {
                cycle.push_back(nv);
                for (int u = v; u != nv; u = parent[u]) cycle.push_back(u);
                cycle.push_back(nv);
                reverse(cycle.begin(), cycle.end());
                return true;
            }
        }
        state[v] = 2;
        return false;
    };
    for (int v = 0; v < n; v++) {
        if (state[v] == 0 && dfs(dfs, v, -1)) break;
    }

    if (cycle.empty()) cout << "No\n";
    else {
        cout << "Yes\n";
        for (int v : cycle) cout << v << ' ';
        cout << '\n';
    }
}

使用例 ​

有向グラフの入力（0-indexed）

text
5 5
0 1
1 2
2 0
2 3
3 4

出力

text
Yes
0 1 2 0

サイクルが存在しない場合は No を出力する。

注意点 ​

  • 有向グラフでは探索中と探索完了を区別する。
  • 無向グラフでは親へ戻る辺を除外する。
  • 無向多重グラフでは平行辺2本もサイクルを構成する。
  • 自己ループもサイクルとして検出できる。
  • 非連結グラフにも対応するため、すべての未訪問頂点からDFSする。
  • 復元されるサイクルは必ずしも最短ではない。
  • 再帰が深くなる場合はスタックオーバーフローに注意する。

別の検出方法 ​

対象方法
有向グラフDFS・トポロジカルソート
無向グラフDFS・Union Find
Functional Graph訪問状態の管理
有向グラフの強連結成分SCC

有向グラフでは、トポロジカルソートで全頂点を列挙できなければ閉路が存在する。

無向グラフでは、Union Findで同じ連結成分に属する2頂点を辺で結ぼうとすると閉路ができる。

関連 ​