双连通分量：点双与边双
代码模板双连通分量（点双与边双）的原理与实现：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 的出栈规则分别正确。
复杂度分析
设点数为
- 时间复杂度：
。 - 空间复杂度：
。
代码实现
点双连通分量：
C++
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;
}
};
Python
python
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
# 无向图 Tarjan 求点双连通分量（v-BCC），顺便标出割点。
# 调用契约：e.reset(); 每条无向边 e.add2(u, v); bcc.set(n); bcc.solve();
# 结果：bcc.bcc[1..bcc_cnt] 是各点双的点集，割点看 bcc.is_cut[u]。
# dfs 改显式栈：无向图可以是 1e5 长链，递归写法会爆 Python 栈；割点可属于多个 BCC，故用点集列表。
from collections import defaultdict
class Edge:
"""链式前向星的边：v 终点、next 下一条出边编号。"""
__slots__ = ("u", "v", "w", "next")
def __init__(self, u: int, v: int, w: int, next: int) -> None:
self.u = u
self.v = v
self.w = w
self.next = next
class LinkList:
"""与 linklist.py 的 linkList 等价的最小实现，保证本文件可独立复制使用。"""
def __init__(self) -> None:
self.reset()
def reset(self) -> None:
self.edge_cnt = 0
self.e: list[Edge] = []
self.h: defaultdict[int, int] = defaultdict(lambda: -1)
def add(self, u: int, v: int, w: int = 0) -> None:
self.e.append(Edge(u, v, w, self.h[u]))
self.h[u] = self.edge_cnt
self.edge_cnt += 1
def add2(self, u: int, v: int, w: int = 0) -> None:
self.add(u, v, w)
self.add(v, u, w)
def __getitem__(self, i: int) -> Edge:
return self.e[i]
e = LinkList()
class TarjanBCC:
"""dfn/low 是时间戳，st 存已访问点；bcc 按下标 1..bcc_cnt 存各分量的点集。"""
def __init__(self) -> None:
self.n = 0
self.timer = 0
self.st: list[int] = []
self.dfn: list[int] = []
self.low: list[int] = []
self.bcc_cnt = 0
self.is_cut: list[bool] = []
self.root = 0
self.bcc: list[list[int]] = []
def set(self, _n: int) -> None:
"""按点数 n 重新分配并清零；bcc 下标 1..n 够用（n 点图至多 n-1 个点双）。"""
self.n = _n
self.timer = 0
self.bcc_cnt = 0
self.dfn = [0] * (_n + 1)
self.low = [0] * (_n + 1)
self.is_cut = [False] * (_n + 1)
self.st = []
self.bcc = [[] for _ in range(_n + 1)]
self.root = 0
def dfs(self, root: int, fa: int) -> None:
"""从 root 出发做点双；fa 挡住直接走回父节点，root 用于根割点特判。"""
self.timer += 1
self.dfn[root] = self.low[root] = self.timer
self.st.append(root)
# 栈帧 [u, fa, 下一条待处理出边编号, 已完成的子节点数, 是否已初始化]
stack: list[list[int]] = [[root, fa, e.h[root], 0, 1]]
while stack:
frame = stack[-1]
u = frame[0]
i = frame[2]
advanced = False
while i != -1:
v = e[i].v
i = e[i].next
if v == frame[1]:
continue # 无向图核心：不走回头边
if self.dfn[v] == 0:
frame[2] = i
self.timer += 1
self.dfn[v] = self.low[v] = self.timer
self.st.append(v)
stack.append([v, u, e.h[v], 0, 1])
advanced = True
break
if self.dfn[v] < self.dfn[u]:
# 返祖边：用 dfn[v] 更新 low[u]（dfn[v] > dfn[u] 的是前向边，忽略）
if self.dfn[v] < self.low[u]:
self.low[u] = self.dfn[v]
if advanced:
continue
# u 的邻边处理完，弹栈；此时父节点刚“递归返回”，做子节点收尾工作。
stack.pop()
if stack:
p = stack[-1]
pu = p[0]
p[3] += 1 # 父节点的子节点计数 child++
if pu != self.root and self.low[u] >= self.dfn[pu]:
self.is_cut[pu] = True
if self.low[u] < self.low[pu]:
self.low[pu] = self.low[u]
if self.low[u] >= self.dfn[pu]:
# v 子树无法绕过 pu 回到更早祖先：弹到 v 为止构成一个点双。
self.bcc_cnt += 1
comp: list[int] = []
while True:
node = self.st.pop()
comp.append(node)
if node == u:
break
comp.append(pu) # pu 也属于该点双，但不出栈（它可能属于多个分量）
self.bcc[self.bcc_cnt] = comp
elif u == self.root and frame[3] > 1:
self.is_cut[u] = True # 根是割点当且仅当有至少两棵子树
def solve(self) -> None:
for i in range(1, self.n + 1):
if self.dfn[i] == 0 and e.h[i] != -1: # 孤立点不产生点双，直接跳过
self.root = i
self.dfs(i, 0)
def cut_cnt(self) -> int:
return sum(1 for i in range(1, self.n + 1) if self.is_cut[i])
边双连通分量：
C++
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);
}
}
}
};
Python
python
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
# Tarjan 求无向图边双连通分量（e-BCC）。依赖模块级链式前向星全局 e（内联最小实现，完整版见 linklist.py）：
# e.reset(); e.add2(u, v)
# t = TarjanEBCC(); t.set(n); t.solve(); t.bcc_cnt / t.bcc_id[1..n]
# 与割边共用 low 数组：low[u] == dfn[u] 时弹栈，栈中 u 及其上面的点构成一个 e-BCC。
# 这里用父节点 fa 挡回头边（与 C++ 一致，重边会被误判为父边）；点编号 1..n。
# dfs 递归深度最坏 n（1e5+），使用前需 sys.setrecursionlimit(1 << 20)。
from collections import defaultdict
class Edge:
"""链式前向星的边：v 终点、next 同起点的下一条边编号。"""
__slots__ = ("u", "v", "w", "next")
def __init__(self, u: int, v: int, w: int, next: int) -> None:
self.u = u
self.v = v
self.w = w
self.next = next
class LinkList:
"""与 linklist.py 的 linkList 等价的最小实现，保证本文件可独立复制使用。"""
def __init__(self) -> None:
self.reset()
def reset(self) -> None:
self.edge_cnt = 0
self.e: list[Edge] = []
self.h: defaultdict[int, int] = defaultdict(lambda: -1)
def add(self, u: int, v: int, w: int = 0) -> None:
self.e.append(Edge(u, v, w, self.h[u]))
self.h[u] = self.edge_cnt
self.edge_cnt += 1
def add2(self, u: int, v: int, w: int = 0) -> None:
self.add(u, v, w)
self.add(v, u, w)
def __getitem__(self, i: int) -> Edge:
return self.e[i]
e = LinkList()
class TarjanEBCC:
"""st 保存当前 DFS 路径上的点；bcc_id[u] ∈ [1, bcc_cnt] 表示 u 所属的 e-BCC。"""
def __init__(self) -> None:
self.n = 0
self.timer = 0
self.st: list[int] = []
self.dfn: list[int] = []
self.low: list[int] = []
self.bcc_cnt = 0
self.bcc_id: list[int] = []
def set(self, _n: int) -> None:
self.n = _n
self.timer = 0
self.bcc_cnt = 0
self.dfn = [0] * (_n + 1)
self.low = [0] * (_n + 1)
self.bcc_id = [0] * (_n + 1)
self.st = []
def dfs(self, u: int, fa: int) -> None:
self.timer += 1
self.dfn[u] = self.low[u] = self.timer
self.st.append(u)
i = e.h[u]
while i != -1:
v = e[i].v
if v != fa: # 无向图核心：不走回头路
if self.dfn[v] == 0:
self.dfs(v, u)
if self.low[v] < self.low[u]:
self.low[u] = self.low[v]
elif self.dfn[v] < self.low[u]:
self.low[u] = self.dfn[v]
i = e[i].next
# low[u] == dfn[u]：u 是所在边双的「根」，栈顶到 u 的点同属一个分量。
if self.low[u] == self.dfn[u]:
self.bcc_cnt += 1
while True:
node = self.st.pop()
self.bcc_id[node] = self.bcc_cnt
if node == u:
break
def solve(self) -> None:
for i in range(1, self.n + 1):
if self.dfn[i] == 0:
self.dfs(i, 0) # fa = 0 是 1..n 之外的哨兵
测试用例
考虑无向图：
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”);