双连通分量：点双与边双
双连通分量（点双与边双）的原理与实现：Tarjan 算法求割点、割边与双连通分量。
一句话算法
点双围绕割点切图，边双围绕桥切图；Tarjan 用 low 判断什么时候形成一个双连通块。
问题模型
双连通分量分两类：
- 点双连通分量 v-BCC：任意两点之间至少有两条点不重复路径；割点可能属于多个点双。
- 边双连通分量 e-BCC：任意两点之间至少有两条边不重复路径；桥会把不同边双隔开。
它们都用于分析无向图的连通性，但切分依据不同：
- 点双怕删点；
- 边双怕删边。
核心直觉
点双
当 DFS 树边 u -> v 满足：
说明 v 子树不能绕过 u 到达 u 的祖先，于是 u 是一个分界点。此时 v 子树中刚刚形成的一段点，加上 u，构成一个点双。
关键区别：割点 u 可能属于多个点双，所以不能像 SCC 那样把 u 彻底弹出并归属到唯一分量。
边双
桥是边双之间的边界。若一条树边 u -> v 满足：
它就是桥。去掉所有桥后，每个连通块就是一个边双。
模板中的 e-BCC 写法是在 Tarjan 过程中用 low[u] == dfn[u] 出栈形成分量。
算法步骤
v-BCC
- DFS 时把访问到的点入栈。
- 对树边
u -> v回溯后，如果low[v] >= dfn[u]：- 新建一个点双；
- 从栈顶弹出直到
v； - 把这些点加入当前点双；
- 再额外把
u加入当前点双。
u不应被这个过程弹掉，因为它可能还属于其他点双。- 用根节点子树数量判断根是否为割点。
e-BCC
- DFS 维护
dfn和low。 - 当
low[u] == dfn[u]时，说明以u为根形成一个边双连通块。 - 从栈顶弹出直到
u，这些点属于同一个 e-BCC。 - 若题目有重边，实际工程中应使用边编号过滤父边，避免把重边误判成桥。
算法证明
v-BCC 正确性
核心不变量：栈中保存当前 DFS 分支上尚未归入某个点双的候选点。
- 若
low[v] >= dfn[u]，v子树无法绕过u回到u的祖先。 - 因此
v子树里刚形成的这部分点与外界的连接必须经过u。 - 这些点加上
u构成一个极大的点双。 u是边界点，可能继续连接其他子树形成其他点双，所以只加入当前分量，不从栈中彻底删除。
e-BCC 正确性
核心不变量：一个 e-BCC 内部不存在桥。
- 若两个点之间的连接依赖某条桥，则它们不可能在同一个边双中。
- Tarjan 的
low能识别无法回到更早祖先的位置。 - 当
low[u] == dfn[u]，栈顶到u的点形成一个无法继续向上合并的边双块。 - 所有跨块边都是桥，块内边都处在某种环状替代路径中。
因此 v-BCC 和 e-BCC 的出栈规则分别正确。
复杂度分析
设点数为
- 时间复杂度：
。 - 空间复杂度：
。
代码实现
点双连通分量：
cpp
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*
代码细节解释：
0. 此代码同时点双连通分量 和 割点. 因为 求 v-bcc 的时候,通常都会问: 哪些点是割点
1. **`std::vector<int> bcc[maxn]`**:
* 与 SCC 不同，SCC 中每个点只属于一个分量，可以用 `id[u]` 数组标记。
* 在点双 (v-BCC) 中，**割点**会同时属于多个 BCC。因此，我们通常用 `vector` 列表来保存每个 BCC 里有哪些点，而不是给每个点打唯一的 ID 标记。
2. **`st.push(u)` 与出栈逻辑**:
* 我们将点入栈。
* 当满足 `low[v] >= dfn[u]` 时，说明找到了一个以 `u` 为“顶端”的双连通分量。
* 我们不断 `pop` 直到弹出 `v`。
* **关键点**：`u` 也是这个分量的一部分，需要 `bcc[...].push_back(u)`，但是 **`u` 不能出栈**。因为 `u` 还是它父节点所在 BCC 的一部分（如果 `u` 不是根），或者是其他子树分支 BCC 的分割点。
3. **`e(u)`**:
* 这里保留了你代码中的 `e(u)` 写法，假设你已经定义了类似 `#define e(u) head[u]` 或者相应的函数来获取邻接表头指针。
这是一个求 **点双连通分量 (v-BCC)** 的模板。
主要区别在于：
1. **无向图 DFS**：需要传入 `father` 参数防止走回头路（或通过边索引判断）。
2. **出栈时机**：SCC 是在回溯完 `u` 后判断 `low[u] == dfn[u]` 出栈；而 BCC 是在处理子节点 `v` 时，若发现 `low[v] >= dfn[u]`，则说明 `v` 及其子树无法绕过 `u` 到达更早的祖先，此时 `u` 和 `v` 的子树构成一个点双。
3. **割点特性**：一个割点 (Articulation Point) 可以属于多个点双连通分量。
*/
struct TarjanBCC {
int n, timer;
std::stack<int> st;
int dfn[maxn], low[maxn];
int bcc_cnt; // BCC 计数
bool is_cut[maxn];
int root; //记录根节点
std::vector<int> bcc[maxn]; // 存储每个 BCC 包含的具体节点
void set(int _n) {
n = _n;
timer = bcc_cnt = 0;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(is_cut,0,sizeof(is_cut));
while (!st.empty()) st.pop();
for (int i = 0; i <= n; i++) bcc[i].clear();
}
// 无向图，需要 fa 参数防止直接走回父节点
void dfs(int u, int fa) {
dfn[u] = low[u] = ++timer;
st.push(u);
int child = 0;
for (int i = e.h[u]; ~i; i = e[i].next) {
int v = e[i].v;
if (v == fa) continue; // 无向图核心：不走回头路
if (!dfn[v]) { // 如果 v 没被访问过
dfs(v, u);
child++;
if(u != root && low[v] >= dfn[u]) {
is_cut[u] = 1;
}
// 更新 low 值
low[u] = std::min(low[u], low[v]);
// 核心判断：low[v] >= dfn[u] 说明 v 没法回到 u 的祖先
// 此时 u 是割点（或者根），u-v 这条边及其下方的点构成一个 BCC
if (low[v] >= dfn[u]) {
bcc_cnt++;
while (true) {
int node = st.top(); st.pop();
bcc[bcc_cnt].push_back(node);
if (node == v) break; // 只要弹到 v 为止
}
// 注意：u 也是这个 BCC 的一部分，但 u 可能属于多个 BCC，
// 所以 u 不能出栈，只是把 u 加入到当前 BCC 列表中
bcc[bcc_cnt].push_back(u);
}
} else if (dfn[v] < dfn[u]) { // 返祖边
low[u] = std::min(low[u], dfn[v]);
}
}
if( u == root && child > 1)
is_cut[u] = 1;
}
void solve() {
for (int i = 1; i <= n; i++) {
if (!dfn[i] && e.h[i] != -1 ) {
// 此时栈为空，dfs 根节点
// 根节点的特判通常包含在上述 dfs 逻辑中
// 只有当图中有孤立点时，需额外注意栈内残留
root = i;
dfs(i, 0);
// 如果是孤立点或者根节点处理完栈里还有元素（极少见情况，视题目定义而定）
// 实际上标准 v-BCC 逻辑中，上述 dfs 里的 if (low[v] >= dfn[u]) 会处理所有连通块
// 唯一的例外是如果 i 是一个孤立点（没有边的点），它不会进入循环
// 如果需要记录孤立点为 BCC，可以在这里补判
}
}
}
// helper
int cut_cnt() {
int cnt = 0;
for(int i = 1;i <= n ;++i ) // i: 1->n
cnt += is_cut[i];
return cnt;
}
};
边双连通分量：
cpp
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
// 假设外部已经有了前向星/邻接表结构体 e 和 head 数组
// struct Edge { int v, next; } e[maxe]; int h[maxn];
struct TarjanEBCC {
int n, timer;
std::stack<int> st;
int dfn[maxn], low[maxn];
int bcc_cnt; // e-BCC 计数
int bcc_id[maxn]; // 记录每个点属于哪个 e-BCC (1 ~ bcc_cnt)
// 初始化
void set(int _n) {
n = _n;
timer = bcc_cnt = 0;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(bcc_id, 0, sizeof(bcc_id));
while (!st.empty()) st.pop();
}
// e-BCC 的 DFS
// 参数 fa: 父节点，用于防止直接沿反向边回去 (处理无向图)
void dfs(int u, int fa) {
dfn[u] = low[u] = ++timer;
st.push(u);
for (int i = e.h[u]; ~i; i = e[i].next) {
int v = e[i].v;
if (v == fa) continue; // 无向图核心：不走回头路 (若有重边需改用边下标判断)
if (!dfn[v]) {
dfs(v, u);
low[u] = std::min(low[u], low[v]);
} else {
low[u] = std::min(low[u], dfn[v]);
}
}
// 核心区别：当 low[u] == dfn[u] 时，说明 u 是该连通分量的“根”
// 此时栈中 u 及以上的点构成一个完整的 e-BCC
if (low[u] == dfn[u]) {
bcc_cnt++;
while (true) {
int node = st.top();
st.pop();
bcc_id[node] = bcc_cnt; // 标记该点属于哪个分量
if (node == u) break; // 把该分量的点都弹出了
}
}
}
// 入口函数
void solve() {
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
dfs(i, 0);
}
}
}
};
测试用例
考虑无向图：
1 2
2 3
3 1
3 4
4 5
5 3
这张图中，1-2-3 是一个环，3-4-5 是另一个环。点 3 属于两个点双，是割点；但每个环内部没有桥。
应用分类详解
双连通分量用于分析无向图在删点或删边后的稳定性。
一、点双：删点不坏
典型模式： 关注删除一个点后的连通性。
识别信号： 出现“割点”“点双”“关键站点”。
核心建模： 割点连接多个点双，点双内部删掉任意非关键点仍保持连通。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 点双模板 | luogu-P8435 | Tarjan 求 v-BCC |
| 网络关键站 | 割点类题 | 分析割点属于多少个点双 |
二、边双：删边不坏
典型模式： 关注删除一条边后的连通性。
识别信号： 出现“桥”“边双”“至少两条边不重复路径”。
核心建模： 桥连接不同边双；缩点后形成一棵桥树或森林。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 边双模板 | luogu-P8436 | Tarjan 求 e-BCC |
| 加边变双连通 | poj-3352 | 缩点后统计叶子 |
三、缩点后的结构分析
典型模式： 先找双连通块，再在块之间建树。
识别信号： 题目需要统计“块”之间的关系，而不是单个点或边。
核心建模： v-BCC 常形成圆方树思路；e-BCC 缩点后形成桥树。
经典例题
1. luogu-P8435
点双连通分量模板题。重点是割点属于多个点双。
2. luogu-P8436
边双连通分量模板题。重点是桥与边双的关系。
3. poj-3352
边双缩点后的加边问题。缩点成树后，根据叶子数量计算答案。
参考
@include_md(“./模拟练习v-bcc.md”);