双连通分量：割点、桥与树形缩点

在有向图中，Tarjan 算法关注的是“能否互相循环到达”（强连通分量）。而在无向图中，节点之间天然是双向可达的，因此连通性分析的焦点发生了转移——我们开始关注“图的脆弱性与鲁棒性”。

如果破坏了某条道路，或者摧毁了某座核心城市，整个交通网络是否会被硬生生撕裂成几个孤岛？这就是桥、割点与双连通分量要解决的核心问题。

一、核心定义与问题背景

无向图的连通性分析分为两个截然不同的维度：基于“边”的连通，和基于“点”的连通。

桥 (Bridge / 割边)：如果删除某条边 $(u, v)$ 后，原图的连通块数量增加（原本连在一起的图裂开了），这条边就是桥。
边双连通分量 (Edge Double Connected Component, e-DCC)：一个不包含任何“桥”的极大连通子图。
割点 (Cut Vertex)：如果删除某个节点 $u$ 及其相连的所有边后，原图的连通块数量增加，节点 $u$ 就是割点。
点双连通分量 (Vertex Double Connected Component, v-DCC)：一个在子图内部任意两点间都存在两条除端点外点互不相交路径的极大子图。注意：某个点可以是原图的割点，但仍然属于多个 v-DCC。

代码里还会把一条独立边的两个端点记成一个点双块；孤立点单独记成一个块。这是下面模板采用的边界约定。

通俗类比与本质区别：

e-DCC（边双）——防范“道路瘫痪”。城市群之间有多条公路互相兜底，断掉任意一条路，大家依然能绕路互相访问。
v-DCC（点双）——防范“枢纽瘫痪”。城市群之间有多个独立枢纽，哪怕某座核心城市遭遇毁灭打击被彻底抹除，剩下的城市依然能互相访问。
注意：相邻的 e-DCC 之间由一条“桥”连接；相邻的 v-DCC 之间共享一个“割点”。割点可以同时属于多个 v-DCC（它是多个群的公共枢纽）；每个点只属于一个 e-DCC，桥连接分量而不属于其内部。

先抓住“破坏对象”：e-DCC 关心删掉一条边后还能不能绕路；v-DCC 关心删掉一个点后还能不能绕路。割点可以同时属于多个 v-DCC，而桥只属于连接两个相邻 e-DCC 的那条边。

二、核心原理与状态转移逻辑

无向图的 Tarjan 算法依然依赖 dfn 和 low 数组，但由于无向图 DFS 树中绝对不存在横叉边（只可能存在树边和返祖边），逻辑比有向图更纯粹，不再需要 instk 数组来判断节点是否在栈内。

1. 寻找桥与 e-DCC 的转移判定

核心判定式：low[v] > dfn[u]
物理意义透析：从子节点 $v$ 出发，在不走回头路（不经过来时的边）的前提下，拼尽全力往上爬，也爬不到 $u$ 或者 $u$ 的祖先。这就意味着，边 $(u, v)$ 是 $v$ 所在子树与外界沟通的唯一生命线。这条边一旦断裂， $v$ 的子树将彻底失联。因此， $(u, v)$ 绝对是桥。

2. 寻找割点与 v-DCC 的转移判定

核心判定式：low[v] >= dfn[u]
物理意义透析：子节点 $v$ 在不经过父节点 $u$ 的情况下拼尽全力往上爬，最多也只能爬到 $u$ 自己，无法跨越 $u$ 到达更高的祖先。这意味着 $v$ 想要向上走，必须且只能经过枢纽 $u$ 。一旦把 $u$ 挖掉， $v$ 所在子树就彻底封闭了。因此， $u$ 是割点。
根节点的特殊情况：对于 DFS 树的起点（根节点），因为它没有祖先，上述条件必定成立。但根节点被删去是否会导致图断裂，取决于它是否有两个或以上互不相交的子树。如果有，删掉根节点后这些子树就会互相失联，根节点才是割点。

low[v] 可以理解成“子树 $v$ 不经过父边时，最早能回到哪一层”。连父节点也爬不到，就是 low[v] > dfn[u]；不能越过父节点到更早的祖先，就是 low[v] >= dfn[u]。

桥、割点、e-DCC 与 v-DCC 的关系

三、边双连通分量 (e-DCC) 的算法与模板

易错点分析：

在无向图中，两个节点之间可能存在重边（多条边直接相连）。对于 e-DCC，重边提供了“备用道路”，如果有一条重边，那么这两点间的边就不是桥。因此，在 DFS 时不能只记录父节点 fa，而必须记录“来时的边的编号 in_edge”，这样才不会误判重边。

下面的模板计算边双编号 dcc 与桥标记 bridge，输出部分按具体题目补充。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500005;
const int M = 2000005; 
struct Edge {
	int v, id;
};
vector<Edge> node[N];

int dfn[N], low[N], id;
int dcc[N], dc;       // 记录节点所属的 e-DCC 编号
int bridge[M];        // 标记某条边是否为桥
stack<int> stk;

// in_edge 为进入节点 u 所经过的【边的编号】
void dfs(int u, int in_edge) {
	dfn[u] = low[u] = ++id;
	stk.push(u);
	
	for (auto ed : node[u]) {
		int v = ed.v, edge_id = ed.id;
		if (!dfn[v]) {
			dfs(v, edge_id);
			low[u] = min(low[u], low[v]);
			
			// 桥的绝对判定条件
			if (low[v] > dfn[u]) {
				bridge[edge_id] = 1; 
			}
		} else if (edge_id != in_edge) { 
			// 遇到返祖边（且不是刚刚走过来的那条原路）
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	// 到达一个 e-DCC 的最高点，把当前分量的节点一起弹出
	if (dfn[u] == low[u]) {
		dc++;
		int x = 0;
		do {
			x = stk.top();
			stk.pop();
			dcc[x] = dc;
		} while (x != u);
	}
}

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		// 存储边的唯一编号 i，解决重边问题
		node[u].push_back({v, i});
		node[v].push_back({u, i});
	}
	
	// 图可能不连通，需遍历所有节点
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) dfs(i, 0);
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

四、点双连通分量 (v-DCC) 的算法与模板

易错点分析：

重边无影响：割点研究的是“节点枢纽”，两点之间哪怕有 100 条重边，删掉节点后该断还是断。所以 DFS 时只传父节点 fa 即可。
出栈边界差异：一个割点必定连接着至少两个 v-DCC，所以它自身会存在于多个 v-DCC 中。出栈时，只能把栈弹到 $v$ 为止，然后把 $u$ 加进当前 v-DCC 中，但绝不能把 $u$ 从栈里弹出去，因为它还要去匹配其他的 v-DCC！

下面的模板计算割点 cut 与点双集合 vdcc，输出部分按具体题目补充。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500005;
vector<int> node[N];

int dfn[N], low[N], id;
int cut[N], root;          // cut 数组标记该节点是否为割点
vector<int> vdcc[N];       // 记录每个 v-DCC 包含了哪些节点
int sc;
stack<int> stk;

void dfs(int u, int fa) {
	dfn[u] = low[u] = ++id;
	stk.push(u);
	int child = 0; // 记录搜索树上的分支数，专为根节点准备
	
	for (int v : node[u]) {
		if (!dfn[v]) {
			child++;
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			
			// 割点判定与 v-DCC 隔离
			if (low[v] >= dfn[u]) {
				cut[u] = 1; 
				sc++;
				int x = 0;
				// 注意：一直弹到 v 为止！
				do {
					x = stk.top();
					stk.pop();
					vdcc[sc].push_back(x);
				} while (x != v); 
				// 割点 u 也属于当前 v-DCC，但绝不出栈
				vdcc[sc].push_back(u); 
			}
		} else if (v != fa) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	// 根节点特判：没有上级，必须有两个或以上互相独立的子树才算割点
	if (u == root && child < 2) {
		cut[u] = 0;
	}
}

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		if (u == v) continue; // 忽略自环
		node[u].push_back(v);
		node[v].push_back(u);
	}
	
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			root = i;
			// 孤立点特判，单独成为一个 v-DCC
			if (node[i].empty()) {
				vdcc[++sc].push_back(i);
				continue;
			}
			dfs(i, 0);
		}
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

五、洛谷实战演练与树形缩点延伸

无向图通过 Tarjan 处理后，常见的树形结构有两种：把 e-DCC 缩成超级点、把桥保留下来，会得到桥树（或桥森林）；把 v-DCC 与原图节点一起组织，会得到圆方树（或圆方森林）。两者都是无环结构，因此可以把复杂的图论问题降维成树上问题。

两种结构不要混记：边双把每个 e-DCC 缩成一个超级点，桥保留下来形成桥树；圆方树则把原图节点作为圆点，再为每个 v-DCC 建一个方点，连接块与块内节点。只分析割点和各块的关系时，可以省去非割点，使用简化的块割树；若要查询任意原点之间的路径，就保留全部原点。

1. 💡 边双缩点与叶子节点公式 (洛谷 P2860 冗余路径)

问题背景：原图有一些桥，要在图中额外添加最少的边，使得整张图变成一个完整的 e-DCC（无论哪条边断了，图依然连通）。
算法分析：

把每个 e-DCC 缩成一个超级节点，原来的桥变成了连接这些超级节点的“树边”。现在问题变成了：在一棵树上最少加几条边，能消除所有桥？ 不要求最后只剩一个大环。
神级结论：统计缩点树中度数为 1 的节点（叶子节点）的数量 $cnt$ ，最少需要添加 $\lceil \frac{cnt}{2} \rceil$ 条边（代码中写为 (cnt + 1) / 2）。本题只求数量；若进一步要求构造，叶子之间要按合适顺序配对，并不是任意两两相连都行。

2. 💡 点双缩点与圆方树 (洛谷 P3225 矿场搭建)

问题背景：矿场内部通道错综复杂。要在矿场的一些节点建立救援出口，要求无论哪一个节点发生坍塌（假设只塌一个），其他所有节点的人都能跑到至少一个出口。求最少需要建立几个出口，以及方案总数。
算法分析：

坍塌普通节点不会把其余点拆散，但若塌掉的恰好是出口，仍需要备用出口；坍塌割点则会让图分裂。因此本题只需围绕各个 v-DCC 与割点，使用上面的简化块割树来分析：

将每个保留节点作为圆点，将每个 v-DCC 提取出一个虚拟的方点。所有圆点只和它所属的方点连边。

通过求出 v-DCC，统计每个 v-DCC 内部包含的割点数量：
1. 包含 0 个割点（整个图就是一个点双）：必须建 2 个出口以防万一。方案数为 $C_{size}^2$ 。
2. 包含 1 个割点（叶子节点块）：一旦这唯一的割点塌了，块内人员就被困死了。必须在块内建 1 个出口。方案数为 $size - 1$ 。
3. 包含 $\ge 2$ 个割点（中间通道块）：无论哪个割点塌了，人员都可以往另一个割点逃生，无需建出口。

各个叶子块的出口选择互不干扰，所以最少出口数相加、方案数相乘。没有割点时要选两个出口，就是为了让一个出口塌掉后，另一个还在。

六、细节剖析：为什么 e-DCC 要用边编号防重边？

在前面的 e-DCC 模板中，我们强调了 DFS 必须传入 in_edge（来时的边编号）而不是 fa（父节点编号）。这其实是无向图处理重边的一个经典坑点。

如果只记录父节点 fa 会出什么错？ 假设节点 $u$ 和 $v$ 之间有两条直接相连的备用公路（边 $E_1$ 和边 $E_2$ ）。当我们通过 $E_1$ 从 $u$ 走到 $v$ 时，在 $v$ 的邻接表中需要过滤掉回头路。如果只写 if (邻居 != fa)，那么 $v$ 会直接忽略掉所有的 $u$ ！这就导致 $E_2$ 这条备用公路被完全无视了。算法会误以为从 $v$ 没法走其他路回到 $u$ ，从而把 $E_1$ 错误地判定为桥。

边编号的精准识别：每条无向边在输入时都被赋予了一个唯一的 ID。当我们从 $E_1$ （编号 1）进入 $v$ 后，遍历 $v$ 的邻居：

看到走过的 $E_1$ （编号 1）：edge_id == in_edge，这是刚走过的原路，跳过。
看到备用公路 $E_2$ （编号 2）：edge_id != in_edge，这是一条合法的返祖边！此时 $v$ 就可以理直气壮地顺着 $E_2$ 往回看，更新 low[v] = min(low[v], dfn[u])。这样一来， $E_1$ 和 $E_2$ 就构成了一个环，双双摆脱了被误判为桥的命运。

七、桥树与圆方树的结构重构与进阶应用（选学）

缩点（缩环为树）是双连通分量最强大的应用。但因为点双和边双的物理性质不同，它们缩点后的树状结构有着本质区别。

1. 桥树（e-DCC 缩点）与加边连通前提

结构特征：直接把每个 e-DCC 像压缩包一样缩成一个超级节点，原本连接各块的桥就变成了连接这些超级节点的“树边”。

叶子配对补边条件：第五节第 1 小节的 P2860 叶子计数公式要求原图已经连通。原图不连通时，要另行分析各连通块怎样连接，不能随便串起来后就声称得到全局最少加边数。

如果题目进一步要求输出具体加了哪几条边，不能随便把相邻的叶子连起来（那样只会形成很小的局部环）。正确的构造法是：将所有叶子在 DFS 序下排成一排 $L_1, L_2 \dots L_{cnt}$ ，令 $i=1,2,\dots,\lceil cnt/2\rceil$ ，将 $L_i$ 与 $L_{i+\lfloor cnt/2 \rfloor}$ 连边。没有桥时不必加边；叶子为奇数时，中间那个叶子会参与两次配对。这种跨越半棵树的连线，能让新产生的环覆盖尽可能多的树边。

2. 圆方树（v-DCC 缩点）的构建与点权建模直觉

（注：维护路径权值属于进阶考点，通常前置要求熟练掌握最近公共祖先 LCA 与线段树）

结构特征：点双连通分量不能像边双那样直接“拍扁”，因为割点同时属于多个 v-DCC，它不能被独占。为了解决这个重叠问题，圆方树采用了一种二分图结构：

圆点：原图真实存在的每一个节点。
方点：为每一个 v-DCC 创建的虚拟节点代表。
连边规则：原图的边作废。如果一个圆点 $u$ 属于某个 v-DCC，就把 $u$ 和该 v-DCC 对应的方点连一条边。

路径维护的直觉与 $O(N)$ 更新陷阱：假如原图每个城市都有一定的物资（原点有权值），我们查询两个不同点 $u,v$ 之间，所有简单路径能够经过的原点中，最小的点权是多少。在圆方树上，路径总是“圆-方-圆-方-圆”交替。路过一个方点，就代表进入了一个 v-DCC，意味着你可以随意访问这个 v-DCC 内的任何一个圆点。所以，方点的权值理应设为它所连接的所有圆点的极小值。

但这里隐藏着一个致命的性能陷阱：由于一个割点可能连接着几十上百个方点，如果修改了一个割点的物资量，就要同时去更新所有相邻方点的值。这样单次修改操作就可能退化成 $O(N)$ 。

破局点：方点只管儿子，不管父亲 在圆方树指定根节点之后，我们让方点内部的数据结构（比如 multiset）只收集它所有圆点儿子的权值，刻意把作为父亲的那个圆点排除在外。这样一来，任意修改一个圆点时，它作为儿子只会向上更新唯一的一个方点父亲，更新相邻方点的这部分代价降到 $O(\log N)$ （维护 multiset 的开销），再配合树上数据结构维护路径查询。在查询任意两点路径时，如果它们的最近公共祖先（LCA）刚好是一个方点，我们只要在最终答案里，额外把这个方点的圆点父亲的权值拉进来比对一次就足够了。

💡 实战代码：圆方树构建与方点权值收集

下面这段代码完整展示了在求出 v-DCC 时实时构建圆方树，并通过一次树上 DFS 完成方点权值的“只管儿子”式初始化。示范输入为连通无自环图， $2\le n\le10^5$ 、点权绝对值不超过 $10^9$ ；这里只演示建树和初始化，不是完整的动态路径查询程序。当前初始化只从 1 号点开始，仅适用于连通图。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200005; // 空间开两倍：1~n 是圆点，n+1 开始是方点
vector<int> G[N];     // 原图邻接表
vector<int> T[N];     // 圆方树邻接表

int dfn[N], low[N], id_cnt;
stack<int> stk;
int square_cnt;       // 方点计数器，从 n 开始递增

int w[N];             // 圆点（原点）的权值
int square_w[N];      // 方点维护的子节点权值极小值

// 核心模块：Tarjan 提取 v-DCC 并实时构建圆方树
void tarjan(int u) {
	dfn[u] = low[u] = ++id_cnt;
	stk.push(u);
	
	for (int v : G[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			
			// 发现一个新的 v-DCC
			if (low[v] >= dfn[u]) {
				square_cnt++; // 诞生一个新的方点
				int x;
				do {
					x = stk.top(); 
					stk.pop();
					// 圈地运动：把弹出的点与当前方点连边
					T[square_cnt].push_back(x);
					T[x].push_back(square_cnt);
				} while (x != v);
				
				// 割点 u 也属于该 v-DCC，同样与方点连边，但绝不出栈
				T[square_cnt].push_back(u);
				T[u].push_back(square_cnt);
			}
		} else {
			// 这里保留父边也不影响点双的 >= 判定；不要拿这个写法去判桥
			low[u] = min(low[u], dfn[v]);
		}
	}
}

// 树上初始化：让方点收集所有圆点儿子（排除圆点父亲）的信息
void dfs_tree(int u, int fa, int n) {
	if (u > n) square_w[u] = 2e18; // 方点初始为一个极大安全值
	
	for (int v : T[u]) {
		if (v == fa) continue; // 核心：跳过作为父亲的圆点
		
		dfs_tree(v, u, n);
		
		// 如果 u 是方点，v 就是它的圆点儿子，把权值吸纳进来
		if (u > n) {
			square_w[u] = min(square_w[u], w[v]);
		}
	}
}

void solve() {
	int n, m;
	if (!(cin >> n >> m)) return;
	
	for (int i = 1; i <= n; i++) cin >> w[i];
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	square_cnt = n; // 方点编号紧接着原图节点之后
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i);
			// 孤立点特判，单独成为一个连通块
			if (G[i].empty()) {
				square_cnt++;
				T[square_cnt].push_back(i);
				T[i].push_back(square_cnt);
			}
		}
	}
	
	// 假设全图连通，选 1 号点（必然是圆点）作为圆方树的根进行遍历
	dfs_tree(1, 0, n);
	
	// 验证输出：查看各个方点管理的子节点最小权值
	for (int i = n + 1; i <= square_cnt; i++) {
		cout << "方点 " << i << " 维护的最小子节点权值: " << square_w[i] << '\n';
	}
}

/* 独立输入样例：
5 5
10 20 30 40 50
1 2
2 3
3 1
3 4
4 5

期望输出：
方点 6 维护的最小子节点权值: 50
方点 7 维护的最小子节点权值: 40
方点 8 维护的最小子节点权值: 20
*/

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}