グラフのサイクル検出 (閉路検出) by DFS - けんちょんの競プロ精進記録

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

グラフのサイクル検出 (閉路検出) by DFS

テーマ解説記事 DFS サイクル サイクル検出 グラフ 復元 stack どれか1つ求める Functionalグラフ

私たちは、グラフアルゴリズムとして DFS や BFS を学ぶと

などといった例題を次々とこなしていき、グラフ探索スキルを高めていく道を歩んでいくことになります。そんな長い道のりにおいて、脱初級者の登竜門とも言うべき難所として、本記事ではサイクル検出を解説します！

AtCoder でも、ABC-E や水色 diff などでよく出題されるテーマです。

目次

最終的なサイクル検出コードを「4. まとめのコード」で示すので、時間のない方はそこに飛んでもらえたらと思います。Yosupo Judge Library Checker の「Cycle Detection (Directed)」と「Cycle Detection (Undirected)」を通します。

また、ABC でサイクル検出が出題されるとき、与えられるグラフが Functional Graph であるケースが多々あります。その場合は、一般の場合よりも、実装が楽になります。「5. Functional グラフの場合」で触れます。

　

　

1. サイクル検出問題とは

サイクルとは、グラフの隣接する頂点を辿っていて一週するものを言います。有向グラフの場合は、辺の向きに沿っているもののみを指します。したがって、下図の左側はサイクルですが、右側はサイクルではないですね1。

サイクル検出問題とは、与えらえたグラフ (有向の場合も無向の場合もある) がサイクルを含むかどうかを判定する問題です。また本記事では、サイクルが含まれる場合に、サイクルを復元するところまでやりましょう！

  • サイクルが含まれるかどうかを判定する：比較的易しい
  • 実際に含まれるサイクルを復元する：少し難しい

なお、無向グラフの場合、サイクルが含まれるかどうかを判定するだけならば、Union-Find を用いるのが一番簡単でしょう。

　

2. サイクルを含むかどうかの判定

まずは「判定」をします。

2-1. 通常の DFS の復習

グラフ上の DFS と言えば、下のような疑似コードが定番でしょう。頂点 s, t 間が繋がっているかを調べたり、連結成分の個数を求めたりするとき、いつも下のようなコードを書いていると思います。

seen[v] が True であるとは、頂点 v をすでに見ていることを意味します。

(コード 1：DFS のテンプレ)

// グラフを表す型を定義
using Graph = vector<vector<Edge>>;

// 頂点 v を始点とするグラフ G の探索
void dfs(const Graph &G, int v, vector<bool> &seen) {
    seen[v] = true;
    for (const Edge &e : G[v]) {
        int v2 = (辺 e の行き先の頂点);

        // 頂点 v2 がすでに探索済みの場合はスキップ
        if (seen[v2]) continue;

        // 頂点 v2 を再帰的に探索
        dfs(G, v2, seen);
    }
}

2-2. サイクルが含まれるかを判定するコード

サイクルが含まれるかを判定するコードは、上記のコード 1 に少し手を加えることで実現できます。コード 1 でも用いた変数 seen に加えて、次の変数 finished を管理しましょう 。

　

  • seen[v] ← 関数 dfs(G, v) を行きがけ順に通過したかどうかを示す

    • seen[v] が true であることは、dfs(G, v) がすでに呼び出されていることを示す

  • finished[v] ← 関数 dfs(G, v) を帰りがけ順に通過したかどうかを示す

    • finished[v] が true であることは、グラフ G において頂点 v から辿っていくことのできるすべての頂点に対して finished が true になっていることを示す

　

このように「行きがけ順」と「帰りがけ順」を上手に活用して考えることで、サイクル検出ができます。

百聞は一見にしかずということで、サイクルがあるかどうかを判定する疑似コードを示します。seen[v] は行きがけ時に true にするのに対して、finished[v] は帰りがけ時に true にします。

サイクルが検出されたとき、関数 dfs(G, v) が true を返します。

(コード 2：サイクルがあるかを判定する)

// グラフを表す型を定義
using Graph = vector<vector<Edge>>;

// 頂点 v を始点とするグラフ探索でサイクル検出したら true を返す
bool dfs(const Graph &G, int v, vector<bool> &seen,  vector<bool> &finished) {
    seen[v] = true;    // 行きがけ時に true になる
    for (const Edge &e : G[v]) {
        int v2 = (辺 e の行き先の頂点);
        if (v2 が逆戻りの場合) continue;  // 無向グラフの場合は必要

        // 頂点 v2 がすでに探索済みの場合はスキップ 
        if (finished[v2]) continue;

        // サイクル検出
        if (seen[v2] && !finished[v2]) return true;

        // 頂点 v2 を再帰的に探索
        if (dfs(G, v2, seen, finished)) return true;
    }
    finished[v] = true;  // 帰りがけ時に true になる
    return false;
}

2-3. 具体例

たとえば下図のグラフに対して、上のコード 2 を適用してみましょう。ただし、

  • 頂点 0 を始点とした探索を行う
  • DFS において、各頂点では、その頂点から出ている辺のうち、行き先の頂点番号が小さい順に探索していく

ものとします。

順を追ってみていきます。なお今後、図中の頂点の色は次のように「白色」「橙色」「赤色」で示すことにします。

頂点 v の色 seen[v] の値 finished[v] の値
白色 false false
橙色 true false
赤色 true true

橙色が途中状態で、赤色が最終状態です。

　

Step 1：頂点 5 の呼び出しまで

まず dfs(0) を呼び出したあと、頂点 dfs(2), dfs(3), dfs(5) が順に呼び出されていきます。その後、下図の状態となります。

Step 2：頂点 5 に再び戻ってくるまで

その後、dfs(6) を呼び出し、dfs(7) を呼び出します。このとき、頂点 7 から先はもう頂点が存在しないため、finished[7] = true となり、頂点 7 は赤色となります。

そして、再帰を抜けて関数 dfs(6) 内部に戻って、今度は dfs(8) を呼び出します。同様に finished[8] = true となり、頂点 8 は赤色となります。

そして、関数 dfs(6) 内部に戻ったとき、もう頂点 6 から行ける頂点はないため、finised[6] = true となり、頂点 6 も赤色となります。そして、再帰を抜けて関数 dfs(5) 内部に戻ってきます。

この時点で、下図のようになっています。

Step 3：頂点 13 が呼び出されるまで

関数 dfs(5) 内部に戻ってきたあと、次は関数 dfs(9) が呼び出されます。その後も同様に、関数 dfs(11)、dfs(12)、dfs(13) が呼び出されて、下図のようになります。

なお、dfs(12) において、dfs(15) よりも dfs(13) を先に呼び出すことから、頂点 15 は白色のままです。

final：サイクル検出の瞬間

ここで重大局面を迎えます。関数 dfs(13) 内部では、頂点 3 を再び参照することになります。

ここで、頂点 3 は

seen[3] = true だが、finished[3] = false である

ということが大きなポイントです。dfs(3) が終了する前に、再び dfs(3) が呼び出されたということは、サイクルを辿ってきたことの証拠になります。

これがコード 2 の if 文

if (seen[v2] && !finished[v2]) return true;

の意味です。この if 文に入ったならば、サイクルが含まれていることが保証されます。逆に、関数 dfs(v) を呼び出すとき、頂点 v から到達可能なサイクルがあれば、いつかは上記の if 文に必ず入ります。

以上より、コード 2 を用いることで、(頂点 v から到達可能な) サイクルが含まれるかどうかを判定できることがわかりました。

　

3. サイクルの復元

それでは、与えられたグラフにサイクルが含まれるかどうかを判定するだけでなく、具体的なサイクルを復元するところまでやってみましょう。

そこで、まずは素朴に「サイクル検出までに呼び出された頂点 v をすべて記録する」という方法を考えてみます。このとき、たとえば下図のグラフにおいては、橙色と赤色の頂点がすべて記録されることになります。

これでは無駄な枝葉を多く含んでしまいます。そこで、赤色の頂点を除去するために、スタックを使って次のようにします。

サイクル検出までに呼び出された頂点を記録するスタック変数を stack<int> history とする。

  • seen[v] = true となった瞬間に、history.push(v) とする
  • finished[v] = true となった瞬間に、history.pop() とする

こうすることで、関数 dfs の探索終了後には、history は次の図の橙色の頂点のみを含む状態となります。

オタマジャクシみたいな形になっています。最後に、オタマジャクシの尻尾を取り除いて、サイクルのところだけを取り出します。そのために、サイクルを検出した頂点 (上図の頂点 pos) を記録します。

頂点 pos から開始して、グラフを遡っていき、再び頂点 pos にたどり着いたところで遡りを終了します。こうして、サイクルが復元できます！

なお、ここまでのアルゴリズムはすべて O(N + M) の計算量です ( N：頂点数、 M：辺数)。

次の疑似コード 3 では、関数 dfs() は、サイクルを検出した頂点 pos を返すようにしています。サイクルが検出されなかったときは -1 を返します。

(コード 3：サイクルを復元する疑似コード)

// サイクルを検出する
book dfs(const Graph &G, int v, stack<int> &history, vector<bool> &seen,  vector<bool> &finished) {
    seen[v] = true;    // 行きがけ時に true になる
    history.push(v);    // 履歴を残す 
    for (const Edge &e : G[v]) {
        int v2 = (辺 e の行き先の頂点);
        if (v2 が逆戻りの場合) continue;  // 無向グラフの場合は必要

        // 頂点 v2 がすでに探索済みの場合はスキップ 
        if (finished[v2]) continue;

        // サイクル検出
        if (seen[v2] && !finished[v2]) {
            history.push(v2);
            return v2;
        }

        // 頂点 v2 を再帰的に探索
        int pos = dfs(G, v2, history, seen, finished);
        if (pos != -1) return pos;
    }
    finished[v] = true;  // 帰りがけ時に true になる
    history.pop();    // 探索が完全に終了した頂点 (赤色) は履歴から除去する
    return false;
}

// 履歴からサイクルのみを抽出する関数 (pos：サイクルを検出した頂点)
vector<int> reconstruct(int pos, stack<int> &history) {
    vector<int> res;

    // 履歴を遡ってサイクルを形作る
    while (!history.empty()) {
        int v = history.back();
        res.push_back(v);
        history.pop();
        if (v == pos) break;
    }

    // サイクルの向きを正順にする
    reverse(res.begin(), res.end());
    return res;
}

　

4. まとめのコード

ここまでをまとめて、Yosupo Judge Library Checker の問題を通せるライブラリを整備します。

　

4-1. 有向グラフの場合の実装

まずは有向グラフの問題を解きます。

問題概要

N 頂点 M 辺の有向グラフが与えられる。 i 番目の辺は頂点 u_{i}, v_{i} を結ぶ。単純グラフとは限らないが、自己ループはない。

与えられたグラフにサイクルが含まれるならば、辺素なサイクルを 1 つ見つけて報告せよ (存在しない場合は -1 を出力)。

具体的には、サイクルに含まれる辺番号を順番に出力せよ。サイクルが複数含まれるならばどれを出力してもよい。

制約

  • 2 \le N \le 5 \times 10^{5}
  • 1 \le M \le 5 \times 10^{5}

コード

辺番号を管理する必要があるので、重み付き辺を管理する構造体 Edge<T> を用意する実装にしました (今回の重みは辺番号)。

また、この問題では、サイクル検出関数 detect(bool is_prohibit_reverse) において、逆流を許して is_prohibit_reverse = false としています。たとえば辺 (3, 4), (4, 3) があるとき、これもサイクルとみなすようにするためです。

計算量は O(N + M) です。

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

// 辺を表す構造体
template<class T> struct Edge {
    int from, to;
    T val;
    Edge(int f = -1, int t = -1, T v = -1) : from(f), to(t), val(v) {}
};

// グラフを表す型
template<class T> using Graph = vector<vector<Edge<T>>>;

// サイクル検出ソルバー
template<class T> struct CycleDetection {
    // 入力されたグラフ
    Graph<T> G;
    
    // 探索の様子
    vector<bool> seen, finished;
    vector<Edge<T>> history;
    
    // コンストラクタ
    CycleDetection() { }
    CycleDetection(const Graph<T> &graph) { init(graph); }
    void init(const Graph<T> &graph) {
        G = graph;
        seen.assign(G.size(), false);
        finished.assign(G.size(), false);
    }
    
    // サイクル検出
    // return the vertex where cycle is detected
    int dfs(int v, const Edge<T> &e, bool is_prohibit_reverse = true) {
        seen[v] = true;    // 行きがけ時に true になる
        history.push_back(e);    // 履歴を残す
        for (const Edge<T> &e2 : G[v]) {
            // 逆流を禁止する場合は逆流を禁止する
            if (is_prohibit_reverse && e2.to == e.from) continue;
            
            // 頂点 v2 がすでに探索済みの場合はスキップ
            if (finished[e2.to]) continue;

            // サイクルが検出された
            if (seen[e2.to] && !finished[e2.to]) {
                history.push_back(e2);
                return e2.to;
            }

            // 頂点 v2 を再帰的に探索する
            int pos = dfs(e2.to, e2, is_prohibit_reverse);
            if (pos != -1) return pos;
        }
        finished[v] = true;    // 帰りがけ時に true になる
        history.pop_back();    // 探索が完全に終了した頂点 (赤色) は履歴から除去する
        return -1;
    }
    
    // 履歴からサイクルのみを抽出する関数 (pos：サイクルを検出した頂点)
    vector<Edge<T>> reconstruct(int pos) {
        vector<Edge<T>> cycle;
        
        // 履歴を遡ってサイクルを形作る
        while (!history.empty()) {
            const Edge<T> &e = history.back();
            cycle.push_back(e);
            history.pop_back();
            if (e.from == pos) break;
        }
        
        // サイクルの向きを正順にする
        reverse(cycle.begin(), cycle.end());
        return cycle;
    }
    
    // サイクルを返す関数 (is_prohibit_reverse は逆流を許さないかどうか)
    vector<Edge<T>> detect(bool is_prohibit_reverse = true) {
        int pos = -1;
        for (int v = 0; v < (int)G.size() && pos == -1; ++v) {
            if (seen[v]) continue;
            history.clear();
            pos = dfs(v, Edge<T>(), is_prohibit_reverse);
            if (pos != -1) return reconstruct(pos);
        }
        return vector<Edge<T>>();
    }
};

int main() {
    // 有向グラフの受け取り
    int N, M;
    cin >> N >> M;
    Graph<int> G(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(Edge(u, v, i));
    }
    
    // cycle detection
    CycleDetection<int> cd(G);
    const vector<Edge<int>> &res = cd.detect(false);
    
    // 出力
    if (res.empty()) cout << -1 << endl;
    else {
        cout << res.size() << endl;
        for (const Edge<int> &e : res) {
            cout << e.val << endl;
        }
    }
}

　

4-2. 無向グラフの場合の実装

次に無向グラフの問題を解きます。

問題概要

N 頂点 M 辺の無向グラフが与えられる。 i 番目の辺は頂点 u_{i}, v_{i} を結ぶ。単純グラフとは限らない。

与えられたグラフにサイクルが含まれるならば、辺素なサイクルを 1 つ見つけて報告せよ (存在しない場合は -1 を出力)。

具体的には、サイクルに含まれる辺番号と頂点番号を順番に出力せよ。サイクルが複数含まれるならばどれを出力してもよい。

制約

  • 1 \le N \le 5 \times 10^{5}
  • 0 \le M \le 5 \times 10^{5}

コード

有向グラフのために整備したライブラリをそのまま使い回します。

今回は、サイクル検出関数 detect(bool is_prohibit_reverse) において、逆流を禁止して is_prohibit_reverse = true としています。多重辺でない辺 (3, 4) があるときに、その辺を二度使う (3, 4), (4, 3) は辺素サイクルとは認められないためです。

一方、多重辺 (3, 4), (3, 4) があるときは、それらを一度ずつ使う (3, 4), (4, 3) は辺素サイクルと認められます。これについては例外パターンとして最初に検出しておくことにします。

計算量は本質的部分は O(N + M) ですが、以下のコードでは多重辺の検出のために map 型を用いているため、 O(N + M\log N) となっています。

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

// サイクル検出コードは有向グラフの場合と完全に同一なので略

int main() {
    // 有向グラフの受け取り, 多重辺と自己ループは予め除去しておく
    int N, M;
    cin >> N >> M;
    Graph<int> G(N);
    map<pair<int,int>, int> edges;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        
        // 多重辺
        if (u > v) swap(u, v);
        if (edges.count({u, v})) {
            cout << 2 << endl;
            cout << u << " " << v << endl;
            cout << edges[{u, v}] << " " << i << endl;
            return 0;
        }
        
        G[u].push_back(Edge(u, v, i));
        G[v].push_back(Edge(v, u, i));
        edges[{u, v}] = i;
    }
    
    // cycle detection
    CycleDetection<int> cd(G);
    const vector<Edge<int>> &res = cd.detect(true);
    
    // 出力
    if (res.empty()) cout << -1 << endl;
    else {
        cout << res.size() << endl;
        for (const Edge<int> &e : res) cout << e.from << " ";
        cout << endl;
        for (const Edge<int> &e : res) cout << e.val << " ";
        cout << endl;
    }
}

　

5. Functional グラフの場合

特殊なグラフでは、サイクル検出が楽になることがあります。その最たるものが Functional グラフ です。

なお、実際の ABC などでのコンテストでサイクル検出が出題されるとき、与えられるグラフが Functional グラフである場合はとても多い印象です！

　

5-1. Functional グラフとは

Functional グラフは、各頂点 i に対して、その頂点を始点とする有向辺が 1 本だけ出ているような有向グラフです。下図のように、各連結成分ごとにちょうど 1 個ずつ閉路があります (証明はここに)。

このことを、直感的に理解してみましょう。下図のように、Functional グラフ上のある頂点 v を好きに選びます。この頂点 v から出発して、行き先の頂点への移動を繰り返していくことを考えます。

このとき、この移動が無限に続くなどということはあり得ません。したがって、いつかは過去に訪れたことのある頂点に再度戻って来ます。そこから先は、サイクル上でループすることになります。

注意点としては、始点である頂点 v がサイクル上にあるとは限らないことに注意しましょう。

　

5-2. Functional グラフの場合の実装

AtCoder ABC 311 C - Find it! は、まさに「Functional グラフが与えられるので、それに含まれる閉路を 1 つ示せ」という内容でした。

問題概要

頂点数 N、辺数 N の Functional グラフが与えられる。頂点 i からは頂点 A_{i} への辺が接続している。

このグラフにおいて、同一頂点を複数回含まない有向サイクルをひとつ求めてください。具体的には、サイクルに含まれる頂点数と、サイクルをなす頂点を順に出力してください。

(入力例 1 の図)

制約

  • 2 \le N \le 10^{5}

コード

与えられるグラフは連結とは限りません。しかしながら、任意の頂点 v から出発して、有向辺を辿っていくことにより、いつかはサイクルが検出できます。

ここで、頂点 v がサイクルに含まれるとは限らないことに注意しましょう。そこで、頂点 v に対して「辺を辿る」という移動をあらかじめ N 回やっておくことにします。 N 回移動した後の頂点は、サイクル内部にいるはずです (十分な回数の移動をしたため)。

そこで、その頂点 s から出発して、再び頂点 s に戻ってくるまで、有向辺を辿りましょう。こうして有向サイクルを検出できます。

計算量は O(N) です。

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

// G[v] := 頂点 v の行き先の頂点
vector<int> detect_cycle(const vector<int> &G) {
    // 頂点を 1 つ好きに選んで、N 回移動する
    int v = 0;
    for (int i = 0; i < (int)G.size(); ++i) v = G[v];
    
    // 得られた頂点から出発してサイクルを検出する
    vector<int> res;
    int start = v;
    do {
        res.push_back(v);
        v = G[v];
    } while (v != start);
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) { cin >> A[i]; --A[i]; }
    
    // 閉路検出
    const auto &res = detect_cycle(A);
    cout << res.size() << endl;
    for (auto v : res) cout << v+1 << " ";
    cout << endl;
}

　

6. 問題例

これから色々追加していきます。

一般の場合

drken1215.hatenablog.com

drken1215.hatenablog.com

Functional グラフの場合

drken1215.hatenablog.com

drken1215.hatenablog.com

drken1215.hatenablog.com

  1. 微妙な問題として「同じ頂点や辺を二度以上通るもの」をサイクルとして認めるかどうかは文脈によります。本記事では、同じ頂点や辺を二度通るものは、サイクルと呼ばない立場をとることにします。↩