本课时有配套视频讲解，购买后即可观看（永久有效）

双连通分量

一、课上练习

编程练习

点双连通分量：L49909

二、知识总结

✨ 核心思想

双连通分量（Biconnected Component，BCC）是无向图中连通性的更强保证。根据定义的不同，分为两类：

边双连通分量（e-BCC）：不包含桥的极大连通子图。即任意两点之间至少存在两条边不相交的路径。
点双连通分量（v-BCC）：不包含割点的极大连通子图（或者说任意两点之间至少存在两条内部节点不相交的路径）。

两者的区别在于"删除什么不会断开"——边双连通分量对边的删除有鲁棒性，点双连通分量对点的删除有鲁棒性。

✨ 算法原理

边双连通分量（e-BCC）

核心思路：先求出所有桥，然后删除桥后的每个连通分量就是一个 e-BCC。

实现方式：

用 Tarjan 算法求出所有桥。
对图做 DFS/BFS，遍历时不经过桥边，每次遍历到的连通块就是一个 e-BCC。

缩点：将每个 e-BCC 缩为一个点，桥作为新图的边，得到一棵树（或森林）。

点双连通分量（v-BCC）

核心思路：在 Tarjan 求割点的过程中，利用栈来维护当前路径上的边。当发现一个割点（或根节点的一棵子树）时，将栈中的边弹出，这些边及其端点构成一个 v-BCC。

重要性质：

一个割点可能属于多个 v-BCC。
一条边恰好属于一个 v-BCC。
孤立的边（两端点加一条边）也算一个 v-BCC。

✨ 代码实现

边双连通分量

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const int MAXM = 200005;
6
7struct Edge {
8    int to, next;
9} edges[MAXM * 2];
10int head[MAXN], edge_cnt = 0;
11
12int dfn[MAXN], low[MAXN];
13int timer_cnt = 0;
14bool is_bridge[MAXM * 2]; // 标记桥边
15int bcc_id[MAXN];         // 每个节点所属的 e-BCC
16int bcc_cnt = 0;
17int n, m;
18
19void add_edge(int u, int v) {
20    edges[edge_cnt] = {v, head[u]};
21    head[u] = edge_cnt++;
22    edges[edge_cnt] = {u, head[v]};
23    head[v] = edge_cnt++;
24}
25
26// 第一步：Tarjan 求桥
27void tarjan(int u, int from_edge) {
28    dfn[u] = low[u] = ++timer_cnt;
29    for (int i = head[u]; i != -1; i = edges[i].next) {
30        int v = edges[i].to;
31        if (!dfn[v]) {
32            tarjan(v, i);
33            low[u] = min(low[u], low[v]);
34            if (low[v] > dfn[u]) {
35                // 标记这条边和它的反向边为桥
36                is_bridge[i] = is_bridge[i ^ 1] = true;
37            }
38        } else if (i != (from_edge ^ 1)) {
39            low[u] = min(low[u], dfn[v]);
40        }
41    }
42}
43
44// 第二步：不经过桥的 DFS 划分 e-BCC
45void dfs_bcc(int u, int id) {
46    bcc_id[u] = id;
47    for (int i = head[u]; i != -1; i = edges[i].next) {
48        int v = edges[i].to;
49        if (bcc_id[v] || is_bridge[i]) continue; // 跳过已访问和桥边
50        dfs_bcc(v, id);
51    }
52}
53
54int main() {
55    ios::sync_with_stdio(false);
56    cin.tie(nullptr);
57    memset(head, -1, sizeof(head));
58
59    cin >> n >> m;
60    for (int i = 0; i < m; i++) {
61        int u, v;
62        cin >> u >> v;
63        add_edge(u, v);
64    }
65
66    // 求桥
67    for (int i = 1; i <= n; i++) {
68        if (!dfn[i]) tarjan(i, -1);
69    }
70
71    // 划分 e-BCC
72    for (int i = 1; i <= n; i++) {
73        if (!bcc_id[i]) {
74            bcc_cnt++;
75            dfs_bcc(i, bcc_cnt);
76        }
77    }
78
79    cout << "边双连通分量数：" << bcc_cnt << "\n";
80    for (int i = 1; i <= n; i++) {
81        cout << "节点 " << i << " 属于 e-BCC " << bcc_id[i] << "\n";
82    }
83
84    return 0;
85}

点双连通分量

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5vector<int> adj[MAXN];
6int dfn[MAXN], low[MAXN];
7int timer_cnt = 0;
8int n, m;
9
10stack<pair<int,int>> stk;           // 存储边
11vector<vector<int>> vbcc;           // 所有 v-BCC 的节点集合
12
13void tarjan(int u, int fa) {
14    dfn[u] = low[u] = ++timer_cnt;
15    int child_count = 0;
16
17    for (int v : adj[u]) {
18        if (!dfn[v]) {
19            child_count++;
20            stk.push({u, v}); // 树边入栈
21            tarjan(v, u);
22            low[u] = min(low[u], low[v]);
23
24            // 发现一个 v-BCC 的条件
25            bool is_bcc_root = false;
26            if (fa == 0 && child_count >= 1) is_bcc_root = true;  // 根节点每棵子树一个 v-BCC
27            if (fa != 0 && low[v] >= dfn[u]) is_bcc_root = true;  // 非根割点
28
29            if (is_bcc_root) {
30                // 弹出栈中的边直到 (u, v)，收集节点
31                set<int> nodes;
32                pair<int,int> e;
33                do {
34                    e = stk.top();
35                    stk.pop();
36                    nodes.insert(e.first);
37                    nodes.insert(e.second);
38                } while (e != make_pair(u, v));
39
40                vbcc.push_back(vector<int>(nodes.begin(), nodes.end()));
41            }
42        } else if (v != fa && dfn[v] < dfn[u]) {
43            // 返祖边入栈
44            stk.push({u, v});
45            low[u] = min(low[u], dfn[v]);
46        }
47    }
48}
49
50int main() {
51    ios::sync_with_stdio(false);
52    cin.tie(nullptr);
53
54    cin >> n >> m;
55    for (int i = 0; i < m; i++) {
56        int u, v;
57        cin >> u >> v;
58        adj[u].push_back(v);
59        adj[v].push_back(u);
60    }
61
62    for (int i = 1; i <= n; i++) {
63        if (!dfn[i]) tarjan(i, 0);
64    }
65
66    cout << "点双连通分量数：" << vbcc.size() << "\n";
67    for (int i = 0; i < (int)vbcc.size(); i++) {
68        cout << "v-BCC #" << i + 1 << ": ";
69        for (int v : vbcc[i]) cout << v << " ";
70        cout << "\n";
71    }
72
73    return 0;
74}

✨ 执行示例

以图 1-2, 1-3, 2-3, 3-4, 4-5 为例：

边双连通分量：

桥为 (3,4) 和 (4,5)
删除桥后：{1,2,3} 构成一个 e-BCC，{4} 单独一个，{5} 单独一个
共 3 个 e-BCC

点双连通分量：

v-BCC #1：{1, 2, 3}（三角形）
v-BCC #2：{3, 4}（边 3-4）
v-BCC #3：{4, 5}（边 4-5）
割点 3 属于 v-BCC #1 和 #2，割点 4 属于 v-BCC #2 和 #3

✨ 解题步骤详解

明确问题类型：判断需要的是边双连通还是点双连通。
- 如果关注的是"删边"后的连通性 → 边双连通。
- 如果关注的是"删点"后的连通性 → 点双连通。
求 e-BCC：先 Tarjan 求桥，再跳过桥边 DFS 划分分量。
求 v-BCC：在 Tarjan 求割点的同时，用边栈记录并分割 v-BCC。
缩点建新图：
- e-BCC 缩点后得到一棵树。
- v-BCC 缩点后得到一棵"块割树"（Block-Cut Tree），其中 BCC 节点和割点节点交替出现。

✨ 常见错误

混淆 e-BCC 和 v-BCC：两者定义不同，算法不同，不能混用。
v-BCC 中割点被遗漏：割点属于多个 v-BCC，在弹栈时需要包含割点本身。
孤立点的处理：一个没有边的孤立点不构成任何 v-BCC（因为 v-BCC 至少需要一条边），但它自己是一个 e-BCC。
e-BCC 缩点后忘记处理自环：一个 e-BCC 内部的边在缩点后变成自环，应该忽略。
根节点的特殊处理：v-BCC 中根节点的每棵子树都产生一个独立的 v-BCC。

✨ 算法评价

指标	e-BCC	v-BCC
时间复杂度	O(V + E)	O(V + E)
空间复杂度	O(V + E)	O(V + E)
缩点结果	树/森林	块割树
应用	加最少边使图边双连通	加最少边使图点双连通

双连通分量是无向图分析中非常重要的工具，也是许多竞赛题的建模基础。掌握两种 BCC 的区别和各自的求法，对解决图论综合题很有帮助。