边双连通分量 (eBCC) 与缩点详解

type

Post

status

Published

date

May 3, 2026

slug

ebcc

summary

一、核心概念：割边与边双连通分量

在深入算法之前，我们必须先理清几个图论中的基础定义。

割边（Bridge / 桥）：

在一个无向连通图中，如果删除某条边后，图的连通块数量增加（或者说原本连通的图变得不连通了），那么这条边就被称为割边或桥。

*通俗理解*：割图的命脉。它是一条“单传”的道路，一旦这条路断了，图就被劈成了两半。

边双连通图 (Edge Biconnected Graph)：

一个没有割边的无向连通图。

*通俗理解*：在这个图里，任意两个节点之间，都至少存在两条不相交的路径（指没有公共边的路径）。即使任何一条边被摧毁，这两点依然可以通过另一条路相互到达。

边双连通分量 (Edge Biconnected Component, 简称 eBCC)：

无向图中的极大边双连通子图。

*通俗理解*：在原图中，我们尽可能多地把点和边圈在一起，使得这个圈出来的部分内部没有任何割边。这个圈出来的“最大团伙”就是一个边双连通分量。

二、 Tarjan 算法：时间戳与追溯值

要找出图中的边双连通分量，最经典的武器就是 Tarjan 算法。它的核心思想是对图进行一次深度优先搜索 (DFS)，在搜索的过程中为每个节点打上标记，从而发现图的结构特征。

Tarjan 算法依赖两个极其重要的数组：dfn 和 low。

dfn[u] (DFS Number / 时间戳)：表示在 DFS 遍历时，节点是第几个被访问到的。这个值一旦确定就不再改变。

low[u] (Lowest Reachable Timestamp / 追溯值)：表示从节点出发，只经过其 DFS 树上的子节点，并且最多通过一条非树边（返祖边），能够到达的节点中，最小的 dfn 值。

1. 割边的判定法则

在 DFS 的过程中，假设我们当前在节点，准备向下访问邻居节点。此时边是一条树边。

当及其子树全部遍历完毕后，我们得到了的追溯值 low[v]。此时有一个极其优雅的判定定理：

如果 low[v] > dfn[u]，那么边 就是一条割边。

为什么？

dfn[u] 是的访问时间。

low[v > dfn[u]] 意味着，从或者的子树出发，怎么绕也绕不回去，连都到达不了，更别说的祖先了。

这就说明，和外界沟通的唯一桥梁，就是这条边。如果把砍断，及其子树就彻底孤立了。因此，必是割边。

反之，如果 low[v <= dfn[u]]，说明内部有一条暗道（返祖边）可以通向甚至的上方，此时断了也没关系，因为还有暗道，就不是割边。

2. 特殊情况：重边与父节点

在无向图的 Tarjan 算法中，有一个致命的细节：不要顺着刚刚过来的边走回去。

因为是无向图，如果从走到，接下来 DFS 遍历的邻居时，必然会看到。如果把当成返祖边用来更新 low[v]，那所有的树边都不会被判定为割边了！

注意重边的处理：题目（如 P8436）中往往强调有重边。如果和之间有两条边，那么它们都不是割边。因此，我们判断“不能走回头路”时，不能判断节点编号是否等于父节点，而必须判断边的编号是否等于刚刚走过来的那条边的编号。

三、提取边双连通分量：一步一步的推导

如何把这些 eBCC 提取出来呢？这里使用最优雅且只需一次 DFS 的栈机制（Stack）。

入栈：每次首次访问一个节点时，将它压入栈中。

更新：在 DFS 过程中，不断维护 dfn[u] 和 low[u]。

结算（提取）：在节点的所有边都遍历完毕后，检查是否满足 low[u == dfn[u]]。

如果 low[u] == dfn[u]，说明什么？

说明从出发，无论如何也走不到比更早的节点了。这意味着，如果在 DFS 树上把和的父节点切断（即那条边是割边），及其下方目前还在栈里的节点，就构成了一个完全封闭的、内部没有割边的连通块！

退栈操作：不断从栈顶弹出节点，直到把也弹出来。刚刚弹出的这一批节点，就共同组成了一个边双连通分量。

四、缩点：化繁为简的艺术

求出边双连通分量后，我们往往需要进行缩点 (Graph Shrinking)。

什么是缩点？

既然一个边双连通分量内部任意两点互达，且不存在割边，我们在处理某些宏观连通性问题（比如树上差分、求必经边、LCA）时，其内部结构已经不重要了。我们可以把整个分量“压缩”成一个超级节点。

缩点后的图有什么性质？

把所有的 eBCC 缩成超级节点后，原图中的割边就变成了连接这些超级节点的边。由于没有回路（如果有回路，它们早就被划入同一个 eBCC 了），缩点后的新图必然是一棵树（或者森林）。这棵树被称为 eBCC Tree（边双树）。

将复杂的图转变成树，我们就可以使用各种树上算法了。

缩点的具体实现步骤：

在 Tarjan 弹栈提取 eBCC 时，给每个节点记录它属于哪一个 eBCC：c[u = ebcc_id]。这个数组就像是节点的“身份证号”。

新建一个图。

遍历原图中的所有边。如果和不在同一个分量中（即 c[u != c[v]]），说明这是一条割边。在新的图中，我们在 c[u] 和 c[v] 之间连一条边。

五、 P8436 模板代码详解

下面是完整的 C++ 代码实现，针对大连通分量图做了常数优化，并且清晰地展示了 Tarjan 算法寻找 eBCC 并缩点的全过程。

六、总结

边双连通分量的求解与缩点是一套非常连贯的思维体系：

用 时间戳 dfn 记录探索的脚步。

用 追溯值 low 寻找“抄近路”的可能。

用 重边编号判定 避开回头路。

用栈 stack 收集互相连通的节点群。

最后用 染色数组 c[] 完成宏观层面的图转树（缩点）。

掌握了这一套机制，不仅能够轻松切掉各种 eBCC 的模板题，还能在面对复杂的图论综合题时，拥有一种“将复杂网络抽丝剥茧”的上帝视角。

一、 核心概念：割边与边双连通分量