割边

代码模板

割边（桥）的判定与实现：Tarjan 算法求无向图中删除后使图不连通的边。

  • 图论
  • Tarjan
  • 割边

一句话算法

割边判定看 low[v] > dfn[u]：如果 v 的子树连 u 都回不到，那么边 u-v 就是唯一通道。

问题模型

给定一张无向图。删除某条边后，如果图的连通块数量增加，那么这条边叫做割边，也叫桥。

割边反映的是无向图中的关键连接：

  • 删除它会切断一部分点；
  • 它不在任何环上；
  • 它常用于边双连通分量和网络可靠性分析。

核心直觉

对 DFS 树中的树边 u -> v：

  • 如果 v 的子树能通过返祖边回到 u 或 u 的祖先，那么边 u-v 不唯一；
  • 如果 v 的子树完全回不到 u 或更早位置，那么 u-v 是唯一通道。

因此割边条件是：

low[v]>dfn[u] low[v] > dfn[u]

注意这里必须是 >，不是 >=。如果 low[v] == dfn[u]，说明 v 的子树还能回到 u，边 u-v 在环上，不是桥。

算法步骤

  1. 对每个未访问点 DFS。
  2. 进入点 u 时，令 dfn[u] = low[u] = ++timer。
  3. 枚举边编号 i，终点为 v。
  4. 不走进入边的反向边 i == (in_edge ^ 1)。
  5. 如果 v 未访问：
    • 递归 DFS；
    • 用 low[v] 更新 low[u]；
    • 若 low[v] > dfn[u]，则边 i 和 i^1 是桥。
  6. 如果 v 是祖先，用 dfn[v] 更新 low[u]。

算法证明

核心不变量：low[u] 表示 u 的子树能通过返祖边到达的最早时间戳。

  1. 若 low[v] > dfn[u]，说明 v 子树无法到达 u 或 u 的任何祖先。
  2. 那么从 v 子树到外部，唯一经过 DFS 树的边就是 u-v。
  3. 删除 u-v 后，v 子树与外部断开，所以 u-v 是割边。
  4. 若 low[v] <= dfn[u]，说明存在从 v 子树回到 u 或祖先的边，删除 u-v 仍有替代路径，所以不是割边。

因此判定条件正确。

复杂度分析

设点数为 nn，边数为 mm。

  • 时间复杂度：O(n+m)O(n+m)。
  • 空间复杂度：O(n+m)O(n+m)。

代码实现

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

        // 与求割点不同，求割边时有两个关键点需要注意：
// 1.判定条件更严格：low[v] > dfn[u] (不能取等号)。
// 因为如果 low[v] == dfn[u]，说明 $v$ 还能回到 $u$，那么 $u-v$ 这条边在环上，
// 不是桥。防止走回头路：在无向图中，判定“不走回头路”时，
// 2.不能简单地判断 v != father，因为两个点之间可能存在重边（多条边）。
// 我们需要通过边的编号来判断——即“不要走刚才进来的那条边的反向边”。


struct TarjanBridge {
    int n, timer;
    int dfn[maxn], low[maxn];
    bool is_bridge[maxe * 2]; // 标记边是否为桥 (注意大小是边数)

    void set(int _n) {
        n = _n;
        timer = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(is_bridge, 0, sizeof(is_bridge));
    }

    /*
     * u: 当前节点
     * in_edge: 进入 u 点的那条边的编号 (替代 father 参数)
     * 用于处理重边情况，确保只屏蔽刚才过来的那一条具体的边
     */
    void dfs(int u, int in_edge) {
        dfn[u] = low[u] = ++timer;

        // 遍历以 u 为起点的所有边
        for (int i = e.h[u]; i != -1; i = e[i].next) {
            int v = e[i].v;

            // 判定条件：i 不是“进入 u 的那条边”的反向边
            // in_edge 是进入 u 的边，in_edge ^ 1 是从 u 回去父亲的边
            // 过滤掉刚才过来的那条边的反向边
            if( i == (in_edge ^ 1) ) continue; 

            if (!dfn[v]) { // 树枝边
                dfs(v, i); // 将当前边 i 传入下一层

                low[u] = std::min(low[u], low[v]);

                // 核心：割边判定
                // 必须是 >，不能是 >=。
                // 如果 low[v] > dfn[u]，说明 v 及其子树无法回到 u 或 u 的祖先
                // 
                // 这里的 else if (dfn[v] < dfn[u]) 其实是个很好的防御性编程。
                // 在无向图 DFS 树中，如果 v 已访问且不是父亲，它一定是祖先 (dfn[v] < dfn[u])。
                // 唯一的例外是有重边连接到由 u 刚访问过的子节点（此时 dfn[v] > dfn[u]），
                // 但这种情况不需要更新 low[u]，因为子节点的 low 已经处理过这种情况了。
                if (low[v] > dfn[u]) {
                    is_bridge[i] = is_bridge[i ^ 1] = true;
                }
            }
            else if( dfn[v] < dfn[u] ) { // 回边
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }

    void solve() {
        // 遍历所有连通分量
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) {
                // 对于根节点，没有“进入的边”，传入 -1
                // -1 ^ 1 结果是一个很大的负数或特定值，肯定不会等于正常的边索引(>=0)
                dfs(i, -1);
            }
        }
    }

    // 辅助：获取所有桥 (以 u < v 形式返回)
    std::vector<std::pair<int, int>> get_bridges() {
        std::vector<std::pair<int, int>> ans;
        // edge_cnt 是总边数索引，遍历 0 到 edge_cnt-1
        // 每次 += 2 跳过反向边，避免重复添加
        for (int i = 0; i < edge_cnt; i += 2) {
            if (is_bridge[i]) {
                ans.push_back({e[i ^ 1].v, e[i].v}); // u=e[i^1].v, v=e[i].v
            }
        }
        return ans;
    }
};
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

        # Tarjan 求无向图割边（桥）。依赖模块级链式前向星全局 e（本文件内联了最小实现，完整版见 linklist.py）：
#   e.reset(); e.add2(u, v)   # 必须成对加边，正向边编号为偶数，i ^ 1 是它的反向边
#   t = TarjanBridge(); t.set(n); t.solve(); bridges = t.get_bridges()
# 割边条件 low[v] > dfn[u]（不能取等号）；用 in_edge ^ 1 屏蔽来路，才能正确处理重边。
# 点编号 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 TarjanBridge:
    """dfn/low 为时间戳；is_bridge 按边编号标记，一对反向边同时置位。"""

    def __init__(self) -> None:
        self.n = 0
        self.timer = 0
        self.dfn: list[int] = []
        self.low: list[int] = []
        self.is_bridge: list[bool] = []

    def set(self, _n: int) -> None:
        """按当前边数重新分配；set 与 add2 的先后顺序都可以，solve 里会补足长度。"""
        self.n = _n
        self.timer = 0
        self.dfn = [0] * (_n + 1)
        self.low = [0] * (_n + 1)
        self.is_bridge = [False] * e.edge_cnt

    def dfs(self, u: int, in_edge: int) -> None:
        """in_edge 是进入 u 的那条边的编号（根传 -1），用于屏蔽来路而不是屏蔽父节点。"""
        self.timer += 1
        self.dfn[u] = self.low[u] = self.timer

        i = e.h[u]
        while i != -1:
            v = e[i].v
            # in_edge ^ 1 是来路的反向边；in_edge = -1 时 -1 ^ 1 = -2，不会与合法边号撞车。
            if i != (in_edge ^ 1):
                if self.dfn[v] == 0:  # 树枝边
                    self.dfs(v, i)
                    if self.low[v] < self.low[u]:
                        self.low[u] = self.low[v]
                    # 严格大于：v 子树连 u 都回不到，u-v 才是唯一的通道。
                    if self.low[v] > self.dfn[u]:
                        self.is_bridge[i] = True
                        self.is_bridge[i ^ 1] = True
                elif self.dfn[v] < self.dfn[u]:  # 回边（只取祖先，忽略已处理过的子节点）
                    if self.dfn[v] < self.low[u]:
                        self.low[u] = self.dfn[v]
            i = e[i].next

    def solve(self) -> None:
        # 若 set 在 add2 之前调用，这里按当前边数补足标记数组（新增边默认不是桥）。
        if len(self.is_bridge) < e.edge_cnt:
            self.is_bridge.extend([False] * (e.edge_cnt - len(self.is_bridge)))
        for i in range(1, self.n + 1):
            if self.dfn[i] == 0:
                self.dfs(i, -1)  # 根没有进入边，传 -1

    def get_bridges(self) -> list[tuple[int, int]]:
        """以 (u, v) 形式返回所有桥；只扫偶数号边，避免同一对重复添加。"""
        ans: list[tuple[int, int]] = []
        for i in range(0, e.edge_cnt, 2):
            if self.is_bridge[i]:
                ans.append((e[i ^ 1].v, e[i].v))
        return ans

测试用例

输入图：

4 4
1 2
2 3
3 1
3 4

割边是：

3 4

前三个点构成环，环上的边都不是桥；3-4 是点 4 通向图中其他点的唯一边。

应用分类详解

割边用于识别无向图中的关键连接。

一、网络关键边

典型模式： 删除一条边后网络断开。

识别信号： 题面出现“桥”“关键道路”“断开一条边”。

核心建模： 把道路/线路看作边，求所有桥。

应用场景 经典题目 核心思路
桥模板 poj-3352 求桥后考虑加边
网络可靠性 通信线路类题 找删除后会断开的边

二、边双连通分量

典型模式： 缩掉所有非桥边形成边双。

识别信号： 出现“任意两点之间有两条边不重复路径”。

核心建模： 桥是不同边双之间的边界。

经典例题

1. poj-3352

经典桥与边双题。先求桥，再分析缩点后的叶子数量。

2. luogu-P1656

无向图求桥并按字典序输出。

3. 边双连通分量模板

割边是理解 e-BCC 的前置知识。继续学习本书边双连通分量章节。