cycle_detection
(Graph/cycle_detection.hpp)

• View this file on GitHub
• Last update: 2024-09-24 03:56:55+09:00
• Include: #include "Graph/cycle_detection.hpp"

概要

cycle検出

コンストラクタ

cycle_detection<directed> (int n) directed = true : 有向グラフ　/ directed = false : 無向グラフ　として、n頂点0辺のグラフを生成

関数

• void add_edge(int u, int v) … directed = true : 辺 u -> vを追加 / directed = false : 辺 u <-> v を追加
  • 計算量 $O(1)$
• pair<vec<int>, vec<int>> run(int vertex = -1) … サイクルを探す。 ((サイクルに含まれる頂点), (サイクルに使われた辺の番号(:= 何番目に追加されたか))) を返す。サイクルがない場合、空の配列を返す。頂点及び辺の格納時順は こちらを参照

  • 計算量 $O(

    V

    +

    E

    )$

  • 備考 vertex に値を入れると、指定された頂点が含まれる連結成分についてのみ調べられる。functional graphのサイクル列挙等に使う。
  • 備考2 runは何回呼んでも良い。

Verified with

• verify/Graph_cycle_detection_1.test.cpp
• verify/Graph_cycle_detection_2.test.cpp

Code

template <bool directed> struct cycle_detection {
    int n, ec;
    vector<vector<pair<int, int>>> g;
    cycle_detection(int n) : n(n), ec(0), g(n) {}

    void add_edge(int u, int v) {
        g[u].emplace_back(v, ec);
        if (directed == false) g[v].emplace_back(u, ec);
        ec++;
    }

    pair<vector<int>, vector<int>> run(int vertex = -1) {
        vector<bool> in(n, false);
        vector<bool> out(n, false);
        vector<int> vs;
        vector<int> es;
        const int fin = INT_MAX;
        auto dfs = [&](auto f, int v, int p) -> int {
            bool prev_edge = false;
            in[v] = true;

            for (auto [to, id] : g[v]) {
                if (to == p) {
                    if (directed == false) {
                        if (prev_edge == false) {
                            prev_edge = true;
                            continue;
                        } else {
                            vs.push_back(v);
                            es.push_back(id);
                            out[v] = true;
                            return to;
                        }
                    }
                }

                if (in[to] == true && out[to] == false) {
                    vs.push_back(v);
                    es.push_back(id);
                    out[v] = true;
                    return (v == to ? fin : to);
                }

                if (in[to] == false) {
                    int root = f(f, to, v);
                    if (root != -1 && root != fin) {
                        vs.push_back(v);
                        es.push_back(id);
                        out[v] = true;
                        return (v == root ? fin : root);
                    } else if (root == fin) {
                        out[v] = true;
                        return fin;
                    }
                }
            }
            out[v] = true;
            return -1;
        };

        int s = 0, t = n;
        if (vertex != -1) s = vertex, t = vertex + 1;

        for (int i = s; i < t; i++) {
            if (in[i] == false) {
                dfs(dfs, i, -1);
                if (vs.empty() == false) {
                    reverse(vs.begin(), vs.end());
                    reverse(es.begin(), es.end());
                    return make_pair(vs, es);
                }
            }
        }
        return make_pair(vs, es);
    }
};
/*
@brief cycle_detection
@docs doc/cycle_detection.md
*/

#line 1 "Graph/cycle_detection.hpp"
template <bool directed> struct cycle_detection {
    int n, ec;
    vector<vector<pair<int, int>>> g;
    cycle_detection(int n) : n(n), ec(0), g(n) {}

    void add_edge(int u, int v) {
        g[u].emplace_back(v, ec);
        if (directed == false) g[v].emplace_back(u, ec);
        ec++;
    }

    pair<vector<int>, vector<int>> run(int vertex = -1) {
        vector<bool> in(n, false);
        vector<bool> out(n, false);
        vector<int> vs;
        vector<int> es;
        const int fin = INT_MAX;
        auto dfs = [&](auto f, int v, int p) -> int {
            bool prev_edge = false;
            in[v] = true;

            for (auto [to, id] : g[v]) {
                if (to == p) {
                    if (directed == false) {
                        if (prev_edge == false) {
                            prev_edge = true;
                            continue;
                        } else {
                            vs.push_back(v);
                            es.push_back(id);
                            out[v] = true;
                            return to;
                        }
                    }
                }

                if (in[to] == true && out[to] == false) {
                    vs.push_back(v);
                    es.push_back(id);
                    out[v] = true;
                    return (v == to ? fin : to);
                }

                if (in[to] == false) {
                    int root = f(f, to, v);
                    if (root != -1 && root != fin) {
                        vs.push_back(v);
                        es.push_back(id);
                        out[v] = true;
                        return (v == root ? fin : root);
                    } else if (root == fin) {
                        out[v] = true;
                        return fin;
                    }
                }
            }
            out[v] = true;
            return -1;
        };

        int s = 0, t = n;
        if (vertex != -1) s = vertex, t = vertex + 1;

        for (int i = s; i < t; i++) {
            if (in[i] == false) {
                dfs(dfs, i, -1);
                if (vs.empty() == false) {
                    reverse(vs.begin(), vs.end());
                    reverse(es.begin(), es.end());
                    return make_pair(vs, es);
                }
            }
        }
        return make_pair(vs, es);
    }
};
/*
@brief cycle_detection
@docs doc/cycle_detection.md
*/

Back to top page