連通分量整理

[Hackmd-link]

哪裡寫得不好請用 discord dm 我。

練習題 : https://judge.yosupo.jp/ 的 gragh 中的點雙和邊雙。

Connected Component (連通分量)

DFS-Tree

定義

在 DFS 的過程中，紀錄走訪的節點與邊，形成一棵 DFS-Tree。

有關邊的分類

Tree Edge : DFS 過程中實際走訪所形成的邊

Back Edge Forward Edge Cross Edge
指向 DFS 樹中祖先節點的邊 指向已拜訪過的子孫節點（非直接子節點）的邊 指向其他子樹或已完成探索區域的邊

定理 1

對於無向連通圖 $G=(V,E)$，其 DFS-Tree 中只會出現 Tree Edge 與 Back Edge。

證明：
假設 DFS-Tree 中出現 Cross Edge，則必須存在三個節點 $a,b,c$，使得 $a$ 是 $b,c$ 的祖先，且 $b,c$ 位於不同子樹，並且 $b,c$ 之間有一條邊（這條邊才會被歸類為 Cross Edge）。然而在 DFS 的過程中，當我們從 $a$ 拜訪 $b$ 時，由於 $b,c$ 之間存在邊，DFS 一定會從 $b$ 走到 $c$，使得 $c$ 成為 $b$ 的子孫。如此一來，該邊就會成為 Tree Edge 或 Back Edge，而非 Cross Edge。這與假設矛盾，因此無向連通圖中不會出現 Cross Edge（Forward Edge 同理）。

AP 與 Bridge

定義

AP (Articulation Point, 割點) Bridge (橋)
從連通圖中移除此節點後，圖變得不連通 從連通圖中移除此邊後，圖變得不連通
  • $D(v)$：節點 $v$ 在 DFS 過程中的時間戳（= DFS 深度），定義根節點 $D(root)=0$。
  • $L(v)$：從節點 $v$ 與其子樹出發，最多透過一條 Back Edge 可以到達的節點的最小 DFS 深度（即 low-link value）。

註 : 不難發現 $\forall$back edge $\not \in$ Bridge。

定理 1

若 DFS-Tree 的根節點 $r$ 有至少兩個子樹，則 $r$ 是 AP。

證明：
若 $deg(r) = 1$，刪除 $r$ 之後，DFS Tree 下方的子節點可以直接作為新根，圖仍連通。
但若 $deg(r) \ge 2$，刪除 $r$ 後，其下方的多個子樹將彼此斷開，形成多個連通分量，因此 $r$ 必為 AP。

定理 2

對於 DFS-Tree 上的非根節點 $v$：

$$
v \text{ 是 AP} \iff \exists w \text{ 是 } v \text{ 的子節點，使得 } L(w) \ge D(v)
$$

證明：
(⇒) 若 $v$ 是割點，則刪掉 $v$ 後，至少有一個子樹（以子節點 $w$ 為根）與圖的其他部分斷開。若該子樹存在 back edge 連回 $v$ 的祖先（即 $L(w) < D(v)$），即使刪除 $v$ 也能保持連通，與 $v$ 是割點的假設矛盾。因此必有子節點 $w$ 使 $L(w) \ge D(v)$。

(⇐) 反之，若存在 $w$ 使 $L(w) \ge D(v)$，說明從 $w$ 的子樹中，沒有 back edge 可以連到 $v$ 的祖先。刪掉 $v$ 後，$w$ 的子樹就無法與圖上層連通，因此 $v$ 必為割點。

定理 3

$\text{let v DFS-Tree上一點}, (v, w) 為 bridge\iff \exists w \text{ 是 } v \text{ 的子節點，使得 } L(w)>D(v)$

證明：
同上，因為沒有從 $w$ 的及其子樹出發的 back edge 可以連到 深度$<D(v)$的點，因此若邊 $(v, w)$ 是 bridge。

線性時間求圖上 AP/Bridge 的方法

結合上述定理可得此程式，看你需要對 AP/Bridge 來修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int now, int par) {
    dfn[now]=low[now]=ts++;
    for(auto v:adj[now]) {
        if(v==par) continue;  //這邊如果是有邊權的情況再調整
        if(!dfn[v]) {
            dfs(v, now);
            low[now]=min(low[now], low[v]);
        }
        else low[now]=min(low[now], dfn[v]);
    }
            // if(now != root && low[nb] >= dfn[now]) -> AP
            // if(low[nb] > dfn[now]) -> bridge
    // if(now == root && child >= 2) -> AP
}

Bridge Connected Component

定義

將一張圖 $G(V, E)$，的所有的橋給移除，就會變成橋連通分量(又稱邊雙)。

  • 橋連通分量 = Bridge Connected Component 簡稱 BCC。
  • 性質 : 橋連通分量上的任何一條邊被移除都不會影響橋的連通性，且將原本的橋給放回去後，會變成一棵樹。

定理 1

若$D(w)=L(w)$，則 $w$ 是橋連通分量上的一端點。

證明：
DFS 時，若某個點 沒辦法透過 Back Edge 回到祖先 (更淺的節點)，那麼 DFS Tree 上就會在這個點「切斷」。

實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int now, int par) {
    dfn[now]=low[now]=ts++;
    stk.push(now);
    for(auto v:adj[now]) {
        if(v==par) continue;  //這邊如果是有邊權的情況再調整
        if(!dfn[v]) {
            dfs(v, now);
            low[now]=min(low[now], low[v]);
        }
        else low[now]=min(low[now], dfn[v]);
    }
    if(low[now]==dfn[now]) { //註 1
        int x;
        bcccnt++;
        do {
            x=stk.top();
            bcc[x]=bcccnt;
            stk.pop();
        } while(x!=now);
    }
}

  • 註 1

    遍歷 $v$ 的子樹後，若 $v$ 的子樹沒辦法透過 Back Edge 回到 $v$ 的祖先，則 $v$ 為橋連通分量上的一端點，若 $v$ 的子樹中存在其他橋連通分量，則分量對在遞迴到它時，完成它在 stk 的移除，使 $v$ 的橋連通分量不包含它。

  • 註 2

這是需要圖無重邊才能使用。若圖有重邊可能形成 $G$ 有兩個點兩條無向邊。使圖不存在 Bridge。

為了解決重邊，核心想法是在 DFS 過程中紀錄哪一條邊是橋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//0-based 重邊
struct EdgeBCC{
    int n, m, dep, sz;
    vector<vector<pair<int, int>>> G;
    vector<vector<int>> bcc;
    vector<int> dfn, low, stk, isBridge, bccId;
    vector<pair<int, int>> edge, bridge;

    EdgeBCC(int _n) : n(_n), m(0), sz(0), dfn(n), low(n), G(n), bcc(n), bccId(n) {}

    void add_edge(int u, int v) {
        edge.push_back({u, v});
        G[u].push_back({v, m});
        G[v].push_back({u, m++});
    }

    void dfs(int now, int pre) {
        dfn[now] = low[now] = ++dep;
        stk.push_back(now);

        for (auto [x, id] : G[now]){
            if (!dfn[x]){
                dfs(x, id);
                low[now] = min(low[now], low[x]);
            }else if (id!=pre){
                low[now] = min(low[now], dfn[x]);
            }
        }

        if (low[now]==dfn[now]){
            if (pre!=-1) isBridge[pre] = true;
            int u;
            do{
                u = stk.back();
                stk.pop_back();
                bcc[sz].push_back(u);
                bccId[u] = sz;
            } while (u!=now);
            sz++;
        }
    }

    void get_bcc() {
        isBridge.assign(m, 0);
        dep = 0;
        for (int i=0 ; i<n ; i++){
            if (!dfn[i]) dfs(i, -1);
        }

        for (int i=0 ; i<m ; i++){
            if (isBridge[i]){
                bridge.push_back({edge[i].first , edge[i].second});
            }
        }
    }
};

Biconnected Component

定義

  • 雙連通分量(點雙) = Biconnected Component 也是簡稱 BCC。
  • 性質 : 若一張圖為雙連通則該圖不存在AP。

我們稱圖 $G=(V, E)$ 的雙連通分量 $S\subseteq V$ 滿足以下條件 :

  1. $S$ 是雙連通的。
  2. 無法再加一個點就無法滿足 1.

接著以下圖舉例。

image

可以發現可以把此圖改成下面兩種的雙連通分量。

image

image

不難發現，如果一個點 $v$ 可以同時可能在兩個雙連通分量，那這個點就會是 $G$ 的 $AP$。

從上面我們知道 AP 即為連接不同雙連通分量的「端點」，
因此也能用類似的方式來求出雙連通分量。

不覺得這個跟判斷橋連通很像嗎?
所以我們按照橋連通來實作吧。

但重邊與否應該不影響這邊的實作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
struct BCC {
    int n, timer;
    vector<vector<int>> G;
    vector<int> dfn, low;
    vector<vector<int>> bcc;
    stack<pair<int,int>> stk;
    vector<bool> inBCC;    // 標記哪些點出現在 BCC 中
    vector<char> vis;      // 用於 extractBCC，避免 sort/unique

    BCC(int _n): n(_n), timer(0) {
        G.assign(n, {});
        dfn.assign(n, 0);
        low.assign(n, 0);
        inBCC.assign(n, false);
        vis.assign(n, 0);
    }

    void add_edge(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }

    void dfs(int u, int parent) {
        dfn[u] = low[u] = ++timer;

        for (int v : G[u]) {
            if (!dfn[v]) {
                stk.emplace(u, v);      // 樹邊
                dfs(v, u);
                low[u] = min(low[u], low[v]);

                if (low[v] >= dfn[u]) { // u 是關節點
                    extractBCC(u, v);
                }
            } else if (v != parent && dfn[v] < dfn[u]) {
                stk.emplace(u, v);      // 回邊
                low[u] = min(low[u], dfn[v]);
            }
        }
    }

    void extractBCC(int u, int v) {
        vector<int> comp;
        while (!stk.empty()) {
            auto [x, y] = stk.top(); stk.pop();
            if (!vis[x]) { vis[x] = true; comp.push_back(x); }
            if (!vis[y]) { vis[y] = true; comp.push_back(y); }
            if (x == u && y == v) break;
        }
        if (!comp.empty()) {
            for (int node : comp) {
                inBCC[node] = true;
                vis[node] = false;  // reset for下一次 BCC 使用
            }
            bcc.push_back(comp);
        }
    }

    void get_bcc() {
        for (int i = 0; i < n; i++) {
            if (!dfn[i]) {
                dfs(i, -1);
                if (!stk.empty()) {
                    vector<int> comp;
                    while (!stk.empty()) {
                        auto [x, y] = stk.top(); stk.pop();
                        if (!vis[x]) { vis[x] = true; comp.push_back(x); }
                        if (!vis[y]) { vis[y] = true; comp.push_back(y); }
                    }
                    if (!comp.empty()) {
                        for (int node : comp) {
                            inBCC[node] = true;
                            vis[node] = false;
                        }
                        bcc.push_back(comp);
                    }
                }
            }
        }

        // 單獨出現的點（沒在任何 BCC 中）
        for (int i = 0; i < n; i++) {
            if (!inBCC[i]) {
                bcc.push_back({i});
            }
        }
    }
};
資訊
#程式
連通分量整理
https://flightzzz.github.io/連通分量/
作者
flight
發布於
2025年7月29日
許可協議