有向閉路検出(Directed Cycle Detection)
(graph/cycle_detection_directed.cpp)

• View this file on GitHub
• Last update: 2026-03-23 22:54:37+09:00

説明

有向グラフから 1 つサイクルを見つける。 見つからなければ空配列を返す。 計算量は $O(N + M)$。

できること

• vector<int> cycle_detection_directed(const vector<vector<pair<int, int>>>& g) 辺番号列としてサイクルを返す。存在しなければ空配列を返す

使い方

g[v] に (to, edge_id) を入れて使う。 返る辺番号列は順に辿ると有向サイクルになる。

Verified with

• test/yosupo_cycle_detection_directed.test.cpp

Code

vector<int> cycle_detection_directed(const vector<vector<pair<int, int>>> &g) {
    int n = g.size();
    vector<int> state(n), st_v, st_e;
    vector<int> cycle;
    auto dfs = [&](auto &&self, int v) -> bool {
        state[v] = 1;
        st_v.emplace_back(v);
        for (auto &&[to, id] : g[v]) {
            st_e.emplace_back(id);
            if (state[to] == 0) {
                if (self(self, to)) return true;
            } else if (state[to] == 1) {
                cycle.emplace_back(id);
                for (int i = (int)st_v.size() - 1; st_v[i] != to; --i) {
                    cycle.emplace_back(st_e[i - 1]);
                }
                reverse(cycle.begin(), cycle.end());
                return true;
            }
            st_e.pop_back();
        }
        st_v.pop_back();
        state[v] = 2;
        return false;
    };
    for (int i = 0; i < n; ++i) {
        if (state[i] == 0 && dfs(dfs, i)) return cycle;
    }
    return {};
}

/**
 * @brief 有向閉路検出(Directed Cycle Detection)
 */

#line 1 "graph/cycle_detection_directed.cpp"
vector<int> cycle_detection_directed(const vector<vector<pair<int, int>>> &g) {
    int n = g.size();
    vector<int> state(n), st_v, st_e;
    vector<int> cycle;
    auto dfs = [&](auto &&self, int v) -> bool {
        state[v] = 1;
        st_v.emplace_back(v);
        for (auto &&[to, id] : g[v]) {
            st_e.emplace_back(id);
            if (state[to] == 0) {
                if (self(self, to)) return true;
            } else if (state[to] == 1) {
                cycle.emplace_back(id);
                for (int i = (int)st_v.size() - 1; st_v[i] != to; --i) {
                    cycle.emplace_back(st_e[i - 1]);
                }
                reverse(cycle.begin(), cycle.end());
                return true;
            }
            st_e.pop_back();
        }
        st_v.pop_back();
        state[v] = 2;
        return false;
    };
    for (int i = 0; i < n; ++i) {
        if (state[i] == 0 && dfs(dfs, i)) return cycle;
    }
    return {};
}

/**
 * @brief 有向閉路検出(Directed Cycle Detection)
 */

Back to top page