点双连通块与边栈分解

知道路口 3 是割点，还没有回答“哪些道路属于同一个不会被单个路口切开的区域”。把所有割点删掉也不是答案：几个区域可能需要共同保留路口 3，才能各自说清自己的边界。点双连通块因此划分的是边，允许不同块在割点处共用顶点。本条目从 low 值的返回时刻出发，给出把这些块真正取出来的边栈算法。

形式陈述

输入是有限、无向、无自环的多重图 $G=(V,E)$ ， $V=\{0,\ldots,n-1\}$ 。允许平行边、孤立点和空图；每条边有独立编号 $0,\ldots,m-1$ ，即使端点相同也不能合并身份。本条目的块是至少含一条边、连通且没有割点的极大子图。这里采用二顶点块约定：一条桥及其两个端点构成一个块；两个顶点间的全部平行边也构成一个块。孤立点不输出为空边块。

“没有割点”使用割点与桥里的删除定义：删去一个顶点及其关联边，不增加这个子图的连通分量数。块的极大性同时针对顶点和边，所以同一块两顶点之间存在的原图边全部属于该块。输出满足：每条边恰好在一个块中；一个顶点可以在多个块中。

算法保留 low 值的发现时刻 $\operatorname{tin}[u]$ 、父边 $\operatorname{pe}[u]$ 与 $\operatorname{low}[u]$ ，再加一条“已探索但还没有交付给块”的边栈 $S$ 。这是两种不同的后进先出栈：DFS 帧栈记住下一条要扫描的邻接项，边栈记住尚未封闭的边。只复制帧栈并不能得到块。

按下面四条规则处理一个 DFS 连通分量：

首次发现顶点 $u$ 时，令 $\operatorname{low}[u]=\operatorname{tin}[u]$ 。沿未访问的邻点 $v$ 下探之前，把树边 $e=(u,v)$ 压入 $S$ ，并设置 $\operatorname{pe}[v]=e$ 。
扫描已访问邻点时，只跳过编号等于父边的那条边。若 $\operatorname{tin}[v]<\operatorname{tin}[u]$ ，这是从后代看向祖先的一次非树边扫描：把该边压栈，并用 $\operatorname{tin}[v]$ 降低 $\operatorname{low}[u]$ 。反方向不再压一次。
子树 $v$ 完成、返回 $u$ 时，先用 $\operatorname{low}[v]$ 降低 $\operatorname{low}[u]$ 。若 $\operatorname{low}[v]\ge\operatorname{tin}[u]$ ，从栈顶不断弹边，直到把树边 $(u,v)$ 也弹出；这整段边构成一个输出块。
该连通分量结束时， $S$ 必须为空；再从下一个未访问顶点开始。孤立点只产生一次顶点访问，不产生块。

块封闭条件用 $\ge$ ，桥条件用 $>$ 。相等时，子树可以回到父顶点，却越不过它：边不是桥，但父顶点仍可能隔开两个块。非根顶点在某个孩子返回时满足 $\ge$ 就是割点；根则必须有至少两个 DFS 孩子。根只有一个孩子时，也照常弹出块，不能因为根不是割点而省略输出。

直觉

边栈像一叠尚未分装的道路记录。下探时先放树边，发现一条能返回祖先的边时也放进去。子树返回得越高，这批记录越可能和上方的记录装进同一个块。

关键问题是“这一支还能绕到父顶点的上方吗？”如果能，即 $\operatorname{low}[v]<\operatorname{tin}[u]$ ，现在封袋太早，因为下方的道路和上方仍由绕路连在一起。如果不能，能往外接的最上方关口就是 $u$ ：从进入这一支的树边起，尚未交付的整段记录已经可以封成一个块。

更深处可能已经封过几袋。这些袋子从栈中移走，但共同的接合顶点仍可以出现在当前袋里。弹出的是边，重复使用的是顶点。这正是“边恰好归属一次”和“割点可能属于多个块”能够同时成立的原因。

三个三角区域通过桥或割点相接；7 与 8 之间有两条独立平行边。下方列出六次返回触发的边栈弹出段 — low 返回条件与边块输出

例子与边界

固定顶点 $0,\ldots,11$ ，按下表顺序把边加入两个端点的邻接表；DFS 从最小未访问顶点开始。这样发现时刻恰好是顶点编号。

边编号	端点	边编号	端点
0	$(0,1)$	7	$(3,6)$
1	$(1,2)$	8	$(6,7)$
2	$(2,0)$	9	$(7,3)$
3	$(2,3)$	10	$(7,8)$
4	$(3,4)$	11	$(7,8)$
5	$(4,5)$	12	$(9,10)$
6	$(5,3)$	—	顶点 11 孤立

最终

\operatorname{low}=[0,0,0,3,3,3,3,3,7,9,10,11].

按输出先后给块编号 $B_0,\ldots,B_5$ 。表内边序是实际出栈顺序，不是按编号排序。

返回的孩子 $v\to u$	$\operatorname{low}[v]$ 与 $\operatorname{tin}[u]$	输出块	出栈边编号	块的顶点集
$4\to3$	$3=3$	$B_0$	$6,5,4$	$\{3,4,5\}$
$8\to7$	$7=7$	$B_1$	$11,10$	$\{7,8\}$
$6\to3$	$3=3$	$B_2$	$9,8,7$	$\{3,6,7\}$
$3\to2$	$3>2$	$B_3$	$3$	$\{2,3\}$
$1\to0$	$0=0$	$B_4$	$2,1,0$	$\{0,1,2\}$
$10\to9$	$10>9$	$B_5$	$12$	$\{9,10\}$

看其中两次返回就能抓住算法。 $4\to3$ 时，回边 $(5,3)$ 让 low 降到 3，但没有降到 3 上方，所以弹出三角形的三条边。 $8\to7$ 时，边 10 是父边；边 11 仍必须作为回边保留，使 $\operatorname{low}[8]=7$ 。如果按“邻点等于父顶点”跳过两条边，会把边 10 误报为桥，还会丢掉边 11。

本图割点是 $2,3,7$ ，桥是边 $3,12$ 。顶点 3 同时属于 $B_0,B_2,B_3$ ，但这些块没有共用任何边。根 0 虽然邻接顶点 1 和 2，DFS 却只有孩子 1，因此不是割点；图的度数不能代替 DFS 孩子数。

两个只在顶点 3 相接的三角形没有桥，却仍是两个点双连通块。因而“先删桥，再取连通分量”求的是另一种分解。空图和全孤立点图都输出零个边块；自环则被本接口明确拒绝，因为它的块归属需要另订约定，不能悄悄套入这里的压栈规则。

推论与应用

为什么每次弹出的都是一个块？先看栈的不变量：其中恰好保留已扫描、尚未输出的边；每条边最多压入一次，树边在进入孩子前压入，非树边只在后代方向压入。无向 DFS 没有连接两棵兄弟子树的交叉边，因此一支子树通向外部的边只能回到祖先。

当 $v\to u$ 满足封闭条件时，栈中从 $(u,v)$ 起的剩余段是连通的。已经弹掉的更深块只在一个接合顶点处附着，移走它们的边不会在这个剩余段的树路径上留下断口。删去 $u$ ，剩余段仍由孩子 $v$ 之下的树边连通。再考虑剩余段内的非根顶点 $z$ ：凡仍留在这一段的孩子分支 $w$ ，都有 $\operatorname{low}[w]<\operatorname{tin}[z]$ ；否则这支在返回 $z$ 时就已经单独弹出了。这样的分支存在一条绕过 $z$ 、回到它的真祖先的边，及通向该边的保留树路径。回到的位置不能越过 $u$ ，否则外层的封闭条件不成立。于是删去 $z$ 后，每个下方分支仍能接回上方，剩余段没有割点。

它也不能继续扩成更大的无割点子图。上方、兄弟分支及先前封闭的下方块，分别只能经一个边界顶点接入；并入其中任一部分，就会让这个接合顶点成为割点。因此每次输出都是极大的。最后，每条树边至少会在根的孩子返回时得到封闭，每条非树边随所在段一起弹出，所以每条输入边恰好输出一次。这既证明完整性，也解释了结束时边栈为何必须为空。

代价为什么仍然线性？邻接项恰好扫描 $2m$ 次，边各压栈、出栈一次，顶点各发现一次。取出一个块的顶点集时，参考实现用长度 $n$ 的“最近块编号”数组去重：只扫描本块边的端点，不为每个块重新清空一张长度 $n$ 的表。因而确定性总时间为 $O(n+m+1)$ ，辅助空间与显式输出合计 $O(n+m+1)$ 。动态数组的扩容按总成本摊还计算；核心过程不依赖哈希表的期望查找界，也不对输出排序。只算 low 的版本可以只保存 $O(n)$ 顶点状态，这里额外保存至多 $m$ 条未交付边，不能沿用那个空间界。

这些边块交给块—顶点森林与单点失效查询后，可以回答“删去路口 $x$ ，指定的 $u,v$ 是否仍连通”，而不只是给出一个全局割点标记。完整终端任务要求复算上述弹栈过程，再用真正删点的搜索检验查询。可下载的标准库参考程序使用显式 DFS 帧，长链不依赖语言递归深度。

参考资料

John E. Hopcroft、Robert E. Tarjan，Efficient Algorithms for Graph Manipulation，Stanford 技术报告 STAN-CS-71-207，1971，印刷页 3–4、图 2。原报告扫描件。给出 DFS、low、边栈及线性块分解；原文以无自环简单图为模型。本文用独立边编号扩展到平行边，并把这一扩展写进接口和检验。
NetworkX，biconnected_component_edges 接口及官方实现。明确二顶点块、边唯一归属、顶点可以重叠，并展示非递归边栈实现；其按邻点处理的代码不是本文多重边编号实现的直接替代。

形式陈述 ​

反向链接

形式陈述