跳转至

双连通分量

边双连通分量

在一张连通的无向图中，对于点 \(u\) 和 \(v\)，无论删去哪条边（只能删去一条）都不能使它们不连通，则 \(u\) 和 \(v\) 边双连通。

边双连通具有传递性，即 \(x,y\) 边双连通，\(y,z\) 边双连通，则 \(x,z\) 双连通。

对于一个无向图中的极大边双连通子图，我们称为一个边双连通分量。

模版
C++
 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
struct Graph {
    int n, tot, pcnt;
    vector<vector<int>> adj, na;
    vector<array<int, 2>> edges;
    vector<int> dfn, low;
    vector<bool> in;
    stack<int> st;
    Graph(int n) : n(n), na(n + 1), adj(n + 1), in(n + 1), dfn(n + 1), low(n + 1), tot(0), pcnt(0) { }
    void addEdge(int u, int v) {
        if (u == v) return;
        adj[u].push_back(edges.size());
        edges.push_back({u, v});
        adj[v].push_back(edges.size());
        edges.push_back({v, u});
    }
    void tarjan(int u, int e) {
        dfn[u] = low[u] = ++tot;
        st.push(u);
        in[u] = true;
        for (auto &idx : adj[u]) {
            int to = edges[idx][1];
            if (idx == (e ^ 1)) continue;
            if (!dfn[to]) {
                tarjan(to, idx);
                low[u] = min(low[u], low[to]);
            } else if (in[to]) {
                low[u] = min(low[u], dfn[to]);
            }
        }
        if (low[u] == dfn[u]) {
            pcnt++;
            while (true) {
                int x = st.top();
                st.pop();
                na[pcnt].push_back(x);
                in[x] = false;
                if (x == u) break;
            }
        }
    }
    void ecc() {
        for (int i = 1 ; i <= n ; i++) {
            if (!dfn[i]) {
                tarjan(i, -1);
            }
        }
        na.resize(pcnt + 1);
    }
}; // Graph
// 定义 Graph g(n) 表示一个 n 个点的无向图
// 使用 g.addEdge(u, v) 进行添加无向边 (u, v)
// 使用 g.ecc() 即可求解边双连通分量

点双连通分量

在一张连通的无向图中，对于点 \(u\) 和 \(v\)，无论删去哪个点（只能删去一个，且不能删去 \(u\) 和 \(v\)）都不能使它们不连通，则 \(u\) 和 \(v\) 点双连通。

点双连通不具有传递性。

对于一个无向图中的极大点双连通子图，我们称为一个点双连通分量。

模版
C++
 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
struct Graph {
    int n, rt, tot, pcnt;
    vector<vector<int>> adj, na;
    vector<int> dfn, low;
    stack<int> st;
    Graph(int n) : n(n), na(n + 1), adj(n + 1), dfn(n + 1), low(n + 1), tot(0), pcnt(0) { }
    void addEdge(int u, int v) {
        if (u == v) return;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++tot;
        st.push(u);
        if (u == rt && adj[u].empty()) {
            pcnt++;
            na[pcnt].push_back(u);
            return;
        }
        for (auto &to : adj[u]) {
            if (!dfn[to]) {
                tarjan(to);
                low[u] = min(low[u], low[to]);
                if (low[to] >= dfn[u]) {
                    pcnt++;
                    while (true) {
                        int x = st.top();
                        st.pop();
                        na[pcnt].push_back(x);
                        if (x == to) {
                            break;
                        }
                    }
                    na[pcnt].push_back(u);
                }
            } else {
                low[u] = min(low[u], dfn[to]);
            }
        }
    }
    void vcc() {
        for (int i = 1 ; i <= n ; i++) {
            if (!dfn[i]) {
                rt = i;
                tarjan(i);
            }
        }
        na.resize(pcnt + 1);
    }
}; // Graph
// 定义 Graph g(n) 表示一个 n 个点的无向图
// 使用 g.addEdge(u, v) 进行添加无向边 (u, v)
// 使用 g.vcc() 即可求解点双连通分量