lowlink
(Graph/lowlink.hpp)

View this file on GitHub
Last update: 2025-01-11 19:51:13+09:00
Include: #include "Graph/lowlink.hpp"

概要

無向グラフに対し、lowlinkと呼ばれるアルゴリズムを実行する。
非連結・多重辺・自己ループok。参考 : https://kntychance.hatenablog.jp/entry/2022/09/16/161858

コンストラクタ

lowlink llink(g) … グラフgに対して実行する。計算量 $O(頂点数 + 辺の本数)$

関数

基本的に、関数はない。その代わり、lowlink構造体のメンバ変数にアクセスしてする事で所望のデータを得る。

vec<pair<int, int>> bridges… 橋を列挙した配列を返す。この際、pairに格納される順番/ どちらがfirst, どちらがsecondかは未定義。重複辺がない時、各辺は1回限り格納される。
vec<int> joints … 関節線を入れた配列を返す。頂点の順番は未定義。
- 計算量 $O(1)$

説明

特に、根付き木において

「sがtの先祖」の定義: ｔから上方向の辺のみを辿ってsに到達できる

より、

DFS木において無視される辺が後退辺のみであるとうことは、「上方向に辿るような移動をする辺しか無視されていない」と解釈する事ができる。

これにより、

辺u-vがサイクルに含まれている⇔無視された辺のうち、「vから初めて上に登る動きをするような辺が存在する」

事となり、ここから

low[v] > ord[u]

の式が容易に導ける。

或いは、

low[u] == ord[u]　⇔ uから根の方向に伸びる辺は橋

また、頂点の場合は少し複雑になる。そもそも、頂点の場合は連結性とサイクルに含まれるかどうかということに綺麗な関係が見当たらない。
この場合、「もし連結成分が増えるのならば、根と非連結になる: 定義→根にたどり着けない頂点が誕生する」事を利用する(注意: 根を取り除く場合は別に考える。)。
まず、$u$を取り除いた場合について考える時、考えるのは$u$の子だけで良い。(逆に、それ以外を考えると複雑になる)
ある頂点vが根にたどり着くためには上向の辺を辿っていくしかない。そのため、頂点uが削除された際には、uの子v全てについて「u -> v の辺を逆走せずに、uより上に行けるか？」を判定すれば良く、この計算はlow/inで既に実行済みである。

また、 命題 : 無向グラフに橋が存在しない　⇔ 辺の向きの付け方であって、グラフが強連結であるものが存在する。 が成立する。この時の辺の向きの付け方はdfs木がその条件を満たす。

橋についての条件は、dfs木をとってlow/ordの条件に還元すると議論が進む事がある（そもそも、検出がそれをしている)

特に、dfs木を取った際、無視された辺は後退辺であると言う性質から、他の部分木を無視して考えられる場合がある。

Verified with

Code

struct lowlink {
    using vi = vec<int>;
    using vvi = vec<vi>;
    using pii = pair<int, int>;

    int n;
    vvi tr;  // dfs木に使われる辺のみ 上から下
    vvi aux;  // dfs木に使われない辺のみ  下から上 自己辺もココ
    vi low, in, par;
    vec<pii> bridges;
    vec<int> joints;
    vec<bool> inner_is_joint;
    vec<int> self_edge_cnt;

    lowlink(const vvi &g)
        : n(g.size()),
          tr(n),
          aux(n),
          low(n, 1001001001),
          in(n, -1),
          par(n, -1),
          inner_is_joint(n, false),
          self_edge_cnt(n, 0) {
        int t = 0;
        int r = 0;
        auto dfs = [&](auto f, int v, int p) -> void {
            par[v] = p;
            in[v] = low[v] = t++;
            bool duplication = false;
            for (int to : g[v]) {
                if (in[to] == -1) {
                    tr[v].push_back(to);
                    f(f, to, v);
                } else {
                    if (to != p) {
                        if (in[to] < in[v])
                            aux[v].push_back(to);
                        else if (to == v) {
                            if ((++self_edge_cnt[v]) & 1) aux[v].push_back(to);
                        }
                        chmin(low[v], in[to]);
                    } else if (duplication == false)
                        duplication = true;
                    else {
                        aux[v].push_back(to);
                        chmin(low[v], in[to]);
                    }
                }
            }

            for (int to : tr[v]) {
                chmin(low[v], low[to]);
            }
            // 部分木について、low/inが求まった
            bool isjoint = false;
            for (int to : tr[v]) {
                if (low[to] > in[v]) bridges.emplace_back(v, to);
                if (low[to] >= in[v]) isjoint = true;
            }

            if (v != r && isjoint)
                joints.push_back(v), inner_is_joint[v] = true;
            else if (v == r) {
                if (tr[v].size() > 1)
                    joints.push_back(v), inner_is_joint[v] = true;
            }
        };

        rep(i, 0, n) if (in[i] == -1) {
            r = i;
            dfs(dfs, i, -1);
        }
    }

    bool is_bridge(int u, int v) {
        if (in[u] > in[v]) swap(u, v);
        if (par[v] != u) return false;
        if (low[v] > in[u])
            return true;
        else
            return false;
    }

    bool is_joint(int v) { return inner_is_joint[v]; }
};

/*
@brief lowlink
@docs doc/lowlink.md
*/

#line 1 "Graph/lowlink.hpp"
struct lowlink {
    using vi = vec<int>;
    using vvi = vec<vi>;
    using pii = pair<int, int>;

    int n;
    vvi tr;  // dfs木に使われる辺のみ 上から下
    vvi aux;  // dfs木に使われない辺のみ  下から上 自己辺もココ
    vi low, in, par;
    vec<pii> bridges;
    vec<int> joints;
    vec<bool> inner_is_joint;
    vec<int> self_edge_cnt;

    lowlink(const vvi &g)
        : n(g.size()),
          tr(n),
          aux(n),
          low(n, 1001001001),
          in(n, -1),
          par(n, -1),
          inner_is_joint(n, false),
          self_edge_cnt(n, 0) {
        int t = 0;
        int r = 0;
        auto dfs = [&](auto f, int v, int p) -> void {
            par[v] = p;
            in[v] = low[v] = t++;
            bool duplication = false;
            for (int to : g[v]) {
                if (in[to] == -1) {
                    tr[v].push_back(to);
                    f(f, to, v);
                } else {
                    if (to != p) {
                        if (in[to] < in[v])
                            aux[v].push_back(to);
                        else if (to == v) {
                            if ((++self_edge_cnt[v]) & 1) aux[v].push_back(to);
                        }
                        chmin(low[v], in[to]);
                    } else if (duplication == false)
                        duplication = true;
                    else {
                        aux[v].push_back(to);
                        chmin(low[v], in[to]);
                    }
                }
            }

            for (int to : tr[v]) {
                chmin(low[v], low[to]);
            }
            // 部分木について、low/inが求まった
            bool isjoint = false;
            for (int to : tr[v]) {
                if (low[to] > in[v]) bridges.emplace_back(v, to);
                if (low[to] >= in[v]) isjoint = true;
            }

            if (v != r && isjoint)
                joints.push_back(v), inner_is_joint[v] = true;
            else if (v == r) {
                if (tr[v].size() > 1)
                    joints.push_back(v), inner_is_joint[v] = true;
            }
        };

        rep(i, 0, n) if (in[i] == -1) {
            r = i;
            dfs(dfs, i, -1);
        }
    }

    bool is_bridge(int u, int v) {
        if (in[u] > in[v]) swap(u, v);
        if (par[v] != u) return false;
        if (low[v] > in[u])
            return true;
        else
            return false;
    }

    bool is_joint(int v) { return inner_is_joint[v]; }
};

/*
@brief lowlink
@docs doc/lowlink.md
*/

lowlink (Graph/lowlink.hpp)

概要

コンストラクタ

関数

説明

Verified with

Code

lowlink
(Graph/lowlink.hpp)