EBCC（边双连通分量）#

1. 定义#

边双连通分量（Edge Biconnected Component, e-BCC）是无向图中的一个极大子图，满足：

删掉子图内任意一条边后，这个子图仍然连通。
等价地说，子图内不存在桥。

常见等价结论：

两个点属于同一个 e-BCC，当且仅当它们之间存在至少两条边不相交路径。
把整张图里的所有桥删掉，剩下的每个连通块就是一个 e-BCC。

2. 这个模板能做什么#

这份模板完成了 3 件事：

求无向图中的所有桥。
求所有边双连通分量。
把每个 e-BCC 缩成一个点，得到一棵树或森林。

复杂度：

时间复杂度：O(V + E)
空间复杂度：O(V + E)

3. 核心性质#

3.1 桥的判定#

设 dfn[u] 表示 u 被 DFS 首次访问的时间戳，low[u] 表示：

从 u 出发，
只走 DFS 树边向下，
最多经过一条返祖边，
能回到的最早祖先时间戳。

若 DFS 树边 u -> v 满足：

1
low[v] > dfn[u]

则这条边是桥。

含义是：v 这棵子树无论怎么绕，都回不到 u 或 u 的祖先，所以 u-v 一断，图就被分开了。

3.2 缩点后的图一定无环#

把每个 e-BCC 缩成一个点后：

原图中的桥，变成新图中的边。
新图一定是一棵树或森林。

原因很直接：

如果缩点图里还有环，那么环上的边都不是桥。
这和“缩点图中的边全部来自原图桥”矛盾。

4. 为什么无向图找桥必须用边编号#

这是这类题最容易写错的地方。

在无向图里，一条无向边会拆成两条方向相反的邻接记录。如果你只用“父节点编号”判断回边：

1
if (v == parent) continue;

那么遇到重边时会直接出错。

反例：两个点之间有两条边#

1
1 == 2

如果从 1 走到 2 用的是第一条边，那么从 2 回看 1 时：

第一条边确实是“原路返回”，应该跳过。
第二条边其实是一条合法返祖边，必须参与更新 low。

但如果你写的是 if (v == parent) continue;，这两条边都会被跳过，结果会把本来不是桥的边误判成桥。

所以正确做法是：

给每条无向边一个唯一的 edge_id
DFS 时记录“进入当前点所使用的那条边编号”
只跳过这同一条边，而不是跳过父节点

模板里的关键写法：

1
if (id == in_edge_id) continue;

这是支持重边的标准写法。

5. 模板字段说明#

5.1 边结构#

1
struct Edge {
2
    int to;
3
    int id;
4
};

to：边的终点
id：无向边编号，同一条无向边的两个方向共用同一个 id

5.2 关键数组#

graph[u]：邻接表
dfn[u]：DFS 访问序
low[u]：追溯值
stk：当前 DFS 栈中尚未归属分量的点
is_bridge[id]：第 id 条无向边是否为桥
edccs：每个 e-BCC 内包含哪些点
edcc_id[u]：点 u 属于哪个 e-BCC

6. 模板流程#

6.1 建图#

1
void addEdge(int u, int v) {
2
    graph[u].push_back({v, edge_counter});
3
    graph[v].push_back({u, edge_counter});
4
    is_bridge.push_back(0);
5
    edge_counter++;
6
}

无向边 (u, v) 会被拆成两条邻接边，但共享同一个 edge_id。

6.2 主过程#

1
void build() {
2
    for (int i = 0; i < n; i++) {
3
        if (!dfn[i]) {
4
            tarjan(i, -1);
5
        }
6
    }
7
}

因为原图可能不连通，所以要从每个未访问点出发。

6.3 Tarjan 过程#

核心逻辑：

dfn[u] = low[u] = ++timer
u 入栈
枚举所有邻边
遇到未访问点就递归
回溯时更新 low
若 low[v] > dfn[u]，则 u-v 是桥
若 dfn[u] == low[u]，说明当前形成一个 e-BCC

对应代码里的关键部分：

1
if (!dfn[v]) {
2
    tarjan(v, id);
3
    low[u] = std::min(low[u], low[v]);
4
    if (low[v] > dfn[u]) {
5
        is_bridge[id] = 1;
6
    }
7
} else {
8
    low[u] = std::min(low[u], dfn[v]);
9
}

注意这里返祖边更新必须是：

1
low[u] = min(low[u], dfn[v]);

不能写成 low[v]。这是 Tarjan 的标准写法。

7. 为什么 `dfn[u] == low[u]` 时可以弹出一个 e-BCC#

在这份模板里，栈中存的是“点”。

当 dfn[u] == low[u] 时，说明：

从 u 往下这一整段 DFS 子树，
已经无法通过返祖边再连到 u 上方的点，
所以从栈顶到 u 的这些点恰好构成一个完整的边双连通分量。

代码：

1
if (dfn[u] == low[u]) {
2
    std::vector<int> current_edcc;
3
    int node;
4
    do {
5
        node = stk.back();
6
        stk.pop_back();
7
        current_edcc.push_back(node);
8
        edcc_id[node] = edccs.size();
9
    } while (node != u);
10
    edccs.push_back(current_edcc);
11
}

8. 缩点图怎么建#

模板里的做法：

1
if (edcc_id[u] != edcc_id[v]) {
2
    tree[edcc_id[u]].push_back(edcc_id[v]);
3
}

含义：

若原图一条边的两个端点属于不同 e-BCC
说明它必然是一条桥
那么它就在缩点图中连接这两个分量

注意：

这里得到的是无向图邻接表，所以一条桥会在两个方向各记录一次。
如果你统计缩点图边数，通常要记得除以 2。

9. 使用方式#

1
int n = 5;
2
EBCC solver(n);
3

4
solver.addEdge(0, 1);
5
solver.addEdge(1, 2);
6
solver.addEdge(2, 0);
7
solver.addEdge(1, 3);
8
solver.addEdge(3, 4);
9

10
solver.build();
11

12
// 1. 判断桥
13
for (int id = 0; id < solver.edge_counter; id++) {
14
    if (solver.is_bridge[id]) {
15
        // id 是桥
16
    }
17
}
18

19
// 2. 查看所有 e-BCC
20
for (auto &comp : solver.edccs) {
21
    // comp 是一个边双连通分量中的所有点
22
}
23

24
// 3. 查看点属于哪个 e-BCC
25
int cid = solver.edcc_id[3];
26

27
// 4. 建缩点图
28
auto tree = solver.buildShrunkenGraph();

10. 例子理解#

10.1 图结构#

1
0 - 1 - 3 - 4
2
 \ /
3
  2

其中：

0-1-2-0 构成一个环，不存在桥
1-3 是桥
3-4 是桥

因此 e-BCC 为：

{0, 1, 2}
{3}
{4}

缩点后得到一条链：

1
{0,1,2} - {3} - {4}

11. 常见坑#

11.1 用父节点判回边#

错误写法：

1
if (v == parent) continue;

这会在重边图上出错。

11.2 返祖边用 `low[v]` 更新#