LowLink (with Two Edge Connected Components, Bi Connected Components)
(src/graph/LowLink.hpp)

• View this file on GitHub
• Last update: 2023-01-12 22:28:24+09:00
• Include: #include "src/graph/LowLink.hpp"

TODO

Block Cut Tree

概要

Lowlink による橋と関節点の列挙，その上で二重辺連結成分分解や二重頂点連結成分分解の構成を行う．

Lowlink

• 橋 (bridge) : 取り除くことで連結成分数が増加するような辺．
• 関節点 (articulation point) : 取り除くことで連結成分数が増加するような頂点．
• 後退辺 (back edge) : dfs の際に通過しなかった辺．

橋と関節点を dfs-tree を利用して頂点数及び辺数に対して線形時間で行うのが Lowlink である． 具体的には，dfs-tree での頂点 $v$ の訪問時刻を $ord_v$，$v$ から後退辺を高々一度だけ用いて到達できる頂点集合における $ord$ の最小値を $low_v$ と定義すると，各辺の両端点におけるこれらの値のみから頂点が関節点であるかや辺が橋であるかを判定することが可能である．

二重辺連結成分分解

どの辺を取り除いても連結であるような連結グラフを二重辺連結成分という． 一般のグラフにおいて，橋でないような辺のみを含むグラフの各連結成分は二重辺連結成分をなす． 元のグラフにおいて各二重辺連結成分を縮約してできるグラフは木構造をなす．

二重頂点連結成分分解

どの点とそれに接続する辺を取り除いても連結であるような連結グラフを二重頂点連結成分という． これも二重辺連結成分に比べると少し複雑だが，関節点で区切ることで二重頂点連結成分をなす（関節点を倍化するとわかりやすいかもしれない）．

Block Cut Tree

二重頂点連結成分を縮約して一つの点とみなし，さらに関節点もそれとは独立した点と考えると，これらは木構造をなす． これが Block Cut Tree である．

メンバ関数	効果	時間計算量
LowLink(n)	$n$ 頂点 $0$ 辺のグラフとして初期化する．	$O(n)$
add_edge(u, v)	頂点 $u$ と頂点 $v$ を結ぶ辺を追加する．	$O(1)$
build()	各種構成を行う．	$O(n + m)$

問題例

• AtCoder Regular Contest 062 F - AtCoDeerくんとグラフ色塗り
• Codeforces Round #278 (Div. 1) E. Tourists
• Codeforces Round #310 (Div. 1) E. Case of Computer Network
  • 二重辺連結成分内の辺を向き付けて強連結にしたいときは dfs 木を一つ取って使う辺は根から伸びる方向に，後退辺は逆向きにすることで達成できる．

Links

• 橋と関節点, lowlink - Lilliput Steps
• Block-cut tree - ei1333の日記

Verified with

• test/aoj/GRL_3_A.test.cpp
• test/aoj/GRL_3_B.test.cpp
• test/yosupo/two_edge_connected_components.test.cpp

Code

#pragma once
#include <cassert>
#include <utility>
#include <vector>

struct LowLink {
    int n, m = 0, t = 0, b = 0;
    std::vector<std::vector<int>> G;
    std::vector<std::pair<int, int>> es;
    std::vector<int> ord, low, tecc, bcc, tmp;
    std::vector<bool> is_articulation, is_bridge;

    LowLink(int n) : n(n), G(n), ord(n, -1), low(n), tecc(n, -1), is_articulation(n, false) {}

    void add_edge(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        G[u].emplace_back(m);
        G[v].emplace_back(m);
        es.emplace_back(u, v);
        is_bridge.emplace_back(false);
        bcc.emplace_back();
        m++;
    }

    void build() {
        for (int i = 0; i < n; i++) {
            if (ord[i] != -1) continue;
            dfs1(i, 0, -1);
            dfs2(i, -1);
        }
    }

    std::pair<int, int> operator[](int k) const { return es[k]; }

private:
    void dfs1(int v, int k, int pre) {
        ord[v] = k++, low[v] = ord[v];
        int cnt = 0;
        for (int& e : G[v]) {
            if (e == pre) continue;
            int u = es[e].first ^ es[e].second ^ v;
            if (ord[u] == -1) {
                cnt++;
                dfs1(u, k, e);
                low[v] = std::min(low[v], low[u]);
                if (pre != -1 and ord[v] <= low[u]) is_articulation[v] = true;
                if (ord[v] < low[u]) is_bridge[e] = true;
            } else
                low[v] = std::min(low[v], ord[u]);
        }
        if (pre == -1 and cnt > 1) is_articulation[v] = true;
    }

    void dfs2(int v, int pre) {
        if (pre == -1) tecc[v] = t++;
        for (int& e : G[v]) {
            if (e == pre) continue;
            int u = es[e].first ^ es[e].second ^ v;
            if (tecc[u] == -1 or ord[u] < ord[v]) tmp.emplace_back(e);
            if (tecc[u] >= 0) continue;
            if (ord[v] >= low[u])
                tecc[u] = tecc[v];
            else
                tecc[u] = t++;
            dfs2(u, e);
            if (ord[v] <= low[u]) {
                while (true) {
                    int ne = tmp.back();
                    tmp.pop_back();
                    bcc[ne] = b;
                    if (ne == e) break;
                }
                b++;
            }
        }
    }
};

#line 2 "src/graph/LowLink.hpp"
#include <cassert>
#include <utility>
#include <vector>

struct LowLink {
    int n, m = 0, t = 0, b = 0;
    std::vector<std::vector<int>> G;
    std::vector<std::pair<int, int>> es;
    std::vector<int> ord, low, tecc, bcc, tmp;
    std::vector<bool> is_articulation, is_bridge;

    LowLink(int n) : n(n), G(n), ord(n, -1), low(n), tecc(n, -1), is_articulation(n, false) {}

    void add_edge(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        G[u].emplace_back(m);
        G[v].emplace_back(m);
        es.emplace_back(u, v);
        is_bridge.emplace_back(false);
        bcc.emplace_back();
        m++;
    }

    void build() {
        for (int i = 0; i < n; i++) {
            if (ord[i] != -1) continue;
            dfs1(i, 0, -1);
            dfs2(i, -1);
        }
    }

    std::pair<int, int> operator[](int k) const { return es[k]; }

private:
    void dfs1(int v, int k, int pre) {
        ord[v] = k++, low[v] = ord[v];
        int cnt = 0;
        for (int& e : G[v]) {
            if (e == pre) continue;
            int u = es[e].first ^ es[e].second ^ v;
            if (ord[u] == -1) {
                cnt++;
                dfs1(u, k, e);
                low[v] = std::min(low[v], low[u]);
                if (pre != -1 and ord[v] <= low[u]) is_articulation[v] = true;
                if (ord[v] < low[u]) is_bridge[e] = true;
            } else
                low[v] = std::min(low[v], ord[u]);
        }
        if (pre == -1 and cnt > 1) is_articulation[v] = true;
    }

    void dfs2(int v, int pre) {
        if (pre == -1) tecc[v] = t++;
        for (int& e : G[v]) {
            if (e == pre) continue;
            int u = es[e].first ^ es[e].second ^ v;
            if (tecc[u] == -1 or ord[u] < ord[v]) tmp.emplace_back(e);
            if (tecc[u] >= 0) continue;
            if (ord[v] >= low[u])
                tecc[u] = tecc[v];
            else
                tecc[u] = t++;
            dfs2(u, e);
            if (ord[v] <= low[u]) {
                while (true) {
                    int ne = tmp.back();
                    tmp.pop_back();
                    bcc[ne] = b;
                    if (ne == e) break;
                }
                b++;
            }
        }
    }
};

Back to top page