「一本通 3.6 练习 3」旅游航道

形式化题目

给定一个包含 $m$ 个顶点、 $n$ 条边的无向图 $G = (V, E)$ （图可能不连通，可能存在重边）。定义一条无向边 $e \in E$ 为主要航道（即图论中的割边或桥），当且仅当在图 $G$ 中删去边 $e$ 后，某些点对之间的连通性被破坏（连通分量数量增加）。输入包含多组测试数据，以节点数与边数均为 $0$ 结束。对于每组数据，求该无向图中割边的总数量。

graph LR
    subgraph 样例 1: 环上的边不是割边
        1((1)) --- 2((2))
        2 --- 3((3))
        3 --- 4((4))
        4 --- 5((5))
        2 --- 6((6))
        6 --- 7((7))
        7 --- 8((8))
        8 --- 5
    end
    subgraph 割边
        5 == "割边 (5, 9)" ==> 9((9))
    end

如上图所示，节点 1 到 8 构成包含两个圈的结构，内部任意删除一条边均不破坏连通性；而边 $(5, 9)$ 删除后节点 9 变成孤立点，因此边 $(5, 9)$ 是割边。

正解

思路

1. 朴素判定及其瓶颈

若采用暴力枚举：每次删掉一条边，然后利用广度优先搜索（BFS）或深度优先搜索（DFS）检验全图的连通块数量是否增加。单次遍历复杂度为 $O(m + n)$ ，总复杂度高达 $O(n(m + n))$ 。在 $m, n \leqslant 30000$ 的数据规模下，运算量约在 $10^9$ 级别，显然无法承受。

2. 无向图 DFS 树与返祖边

在线性时间内判定割边，核心在于利用无向图深度优先搜索生成的 DFS 生成树（DFS Tree）：

在无向图的 DFS 过程中，图中的边被分为两类：树边（首次访问某节点时走过的边）和非树边。
无向图 DFS 生成树中不存在横叉边，所有的非树边都连接着子孙节点与祖先节点，称为返祖边（后向边）。

设在 DFS 树上，节点 $u$ 是节点 $v$ 的父节点，树边为 $(u, v)$ ：

若以 $v$ 为根的整棵 DFS 子树内，存在某个节点引出一条返祖边连回到 $u$ 或 $u$ 的祖先节点，则即使删去树边 $(u, v)$ ， $v$ 子树仍可通过该返祖边与树的其余部分保持连通。
若 $v$ 的子树内没有任何一条非树边能够连回到 $u$ 或其祖先，说明子树 $v$ 通往外界的唯一通道就是树边 $(u, v)$ 。一旦删除该边， $v$ 子树必定与外部脱节。

因此，树边 $(u, v)$ 是割边的充要条件是： $v$ 的子树节点无法通过返祖边到达 $u$ 或 $u$ 以前被访问的祖先。

3. Tarjan 算法维护时间戳

为了量化这一判断条件，维护两个核心数组：

$dfn[u]$ ：节点 $u$ 在 DFS 过程中的访问次序（时间戳）。
$low[u]$ ：以 $u$ 为根的 DFS 子树中任意节点，通过至多一条返祖边能回溯到的顶点的最小 $dfn$ 值。

状态转移规则：

初始访问节点 $u$ 时： $dfn[u] = low[u] = ++timer$ 。
遍历 $u$ 的邻接边 $(u, v)$ ：
- 若 $v$ 尚未访问（树边）：对 $v$ 递归遍历，回溯时更新 $low[u] = \min(low[u], low[v])$ 。此时若满足：
  $low[v] > dfn[u]$
  说明 $v$ 及其子树无法到达 $u$ 或其更早的祖先，边 $(u, v)$ 即为一条割边。
- 若 $v$ 已经访问过且该边不是回退到父节点的反向边（返祖边）：更新 $low[u] = \min(low[u], dfn[v])$ 。

4. 重边与栈深度处理

重边处理：两点之间若存在多条重边，则它们不是割边。为了准确区分“反向边”与“平行重边”，为每条无向边分配唯一的 edge_id。遍历时记录当前节点的入边编号 in_edge，只有当边的唯一编号等于 in_edge 时才跳过，平行重边则作为非树边参与更新 $low$ ，避免将重边误判为割边。
避免深层递归：本题点数规模达 $30000$ ，在极端链状图下递归可能导致栈溢出。实现中采用显式栈模拟 DFS 遍历与回溯，彻底杜绝递归限制并提升执行速度。

代码

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 16:06
# update_at: 2026-09-30 16:06

import sys
from collections.abc import Iterator

# 题目数据可能包含多达 30000 个节点，链状图递归会导致深度过大
sys.setrecursionlimit(100000)


def count_bridges(n: int, adj: list[list[tuple[int, int]]]) -> int:
    """计算无向图中割边（桥）的数量。

    使用 Tarjan 算法求割边：当 low[v] > dfn[u] 时，树边 (u, v) 为割边。
    每个邻接点附带边的唯一编号 edge_id，防止沿反向边直接走回父节点。
    图可能不连通，需要遍历所有未访问节点。
    """
    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    timer = 0
    bridges = 0

    # 用迭代 DFS 彻底避免递归爆栈与函数调用开销
    for start in range(1, n + 1):
        if dfn[start]:
            continue
        timer += 1
        dfn[start] = low[start] = timer
        # 栈元素: (当前节点 u, 入边编号 in_edge, 正在遍历的邻接表索引 edge_idx)
        stack = [(start, -1, 0)]

        while stack:
            u, in_edge, idx = stack[-1]
            if idx < len(adj[u]):
                v, eid = adj[u][idx]
                stack[-1] = (u, in_edge, idx + 1)
                if eid == in_edge:
                    continue  # 跳过同一条无向边的反向边
                if dfn[v]:
                    low[u] = min(low[u], dfn[v])
                else:
                    timer += 1
                    dfn[v] = low[v] = timer
                    stack.append((v, eid, 0))
            else:
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > dfn[p]:
                        bridges += 1

    return bridges


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:
        try:
            m = next(data)
            n = next(data)
        except StopIteration:
            break
        if m == 0 and n == 0:
            break

        adj: list[list[tuple[int, int]]] = [[] for _ in range(m + 1)]
        for eid in range(n):
            u, v = next(data), next(data)
            adj[u].append((v, eid))
            adj[v].append((u, eid))

        bridges = count_bridges(m, adj)
        out.append(str(bridges))

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:12
 * update_at: 2026-10-05 06:12
 */
// main.cpp：Tarjan 求无向图割边（桥）数量，用边编号处理重边，用显式栈避免递归爆栈。
#include <cstdio>

const int MAXN = 30005; // 星球（节点）数量上限
const int MAXM = 60015; // 无向边拆成两条有向边后的数量上限

typedef long long ll;

int head[MAXN]; // head[u] 是节点 u 的第一条出边编号，链式前向星
int to[MAXM];   // to[e] 是有向边 e 的终点
int nxt[MAXM];  // nxt[e] 是边 e 的下一条兄弟边
int edge_id[MAXM]; // edge_id[e] 是该有向边所属无向边的唯一编号，用来区分反向边与重边
int edge_cnt;

int dfn[MAXN]; // dfn[u] 是节点 u 在 DFS 中的访问时间戳
int low[MAXN]; // low[u] 是 u 子树内经至多一条返祖边能到达的最小时间戳
int timer;

// DFS 显式栈的一帧：节点 u、进入 u 的边编号 in_edge、正在扫描的出边编号 cur_edge
struct Frame {
    int u;
    int in_edge;
    int cur_edge;
};

Frame stk[MAXN]; // 显式栈，链状图上深度可达 30000，递归会爆栈
int top;

ll m; // 星球数（节点数）
ll n; // 航道数（边数）

// 加入一条从 u 到 v 的有向边，两侧由同一个无向边编号绑定。
void add_edge(int u, int v, int id) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_id[edge_cnt] = id;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 用迭代式 Tarjan 算法统计当前图的割边数量。
ll count_bridges() {
    ll bridges = 0; // 割边数量
    timer = 0;
    for (int i = 1; i <= m; i++) {
        dfn[i] = 0;
        low[i] = 0;
    }

    // 图可能不连通，每个未访问节点都作为一棵 DFS 树的根
    for (int s = 1; s <= m; s++) {
        if (dfn[s] != 0) continue;
        timer++;
        dfn[s] = low[s] = timer;
        top = 0;
        stk[top].u = s;
        stk[top].in_edge = 0;
        stk[top].cur_edge = head[s];
        top++;

        while (top > 0) {
            Frame &f = stk[top - 1];
            int u = f.u;
            if (f.cur_edge != 0) {
                int e = f.cur_edge;
                f.cur_edge = nxt[e];
                int v = to[e];
                if (edge_id[e] == f.in_edge) continue; // 同一条无向边的反向边，跳过
                if (dfn[v] != 0) {
                    // 返祖边（含重边）：用 dfn[v] 更新 low[u]
                    if (dfn[v] < low[u]) low[u] = dfn[v];
                } else {
                    // 树边：访问 v，把 v 入栈
                    timer++;
                    dfn[v] = low[v] = timer;
                    stk[top].u = v;
                    stk[top].in_edge = edge_id[e];
                    stk[top].cur_edge = head[v];
                    top++;
                }
            } else {
                top--; // u 的邻边扫描完毕，出栈并回溯
                if (top > 0) {
                    int p = stk[top - 1].u;
                    if (low[u] < low[p]) low[p] = low[u];
                    // v 子树无法回到 p 或更早的祖先，树边 (p, u) 是割边
                    if (low[u] > dfn[p]) bridges++;
                }
            }
        }
    }

    return bridges;
}

void solve() {
    while (scanf("%lld %lld", &m, &n) == 2) {
        if (m == 0) break; // 以一行 0 结束（样例为 0 0）
        edge_cnt = 0;
        for (int i = 1; i <= m; i++) head[i] = 0;
        for (int i = 1; i <= n; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            add_edge(a, b, i);
            add_edge(b, a, i);
        }
        printf("%lld\n", count_bridges());
    }
}

int main() {
    solve();
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(m + n)$ 。每个顶点入栈出栈各一次，每条无向边正反方向各被扫描常数次，整体遍历完全线性，对于 $m, n \leqslant 30000$ 能在 0.1 秒内处理完毕。
空间复杂度： $\mathcal{O}(m + n)$ 。邻接表存储 $2n$ 条有向边，数组与显式栈空间开销与点数 $m$ 成正比，内存占用约为 30MB 左右，远低于 128MB 的限制。

总结

本题是无向图割边（桥）判定的经典应用。求解的核心在于：

利用 DFS 树没有横叉边的性质，将连通性判定转化为子树是否存在连回祖先的返祖边；
借由 $dfn$ 与 $low$ 两个时间戳数组将子树可达性转化为简单的数值比较 $low[v] > dfn[u]$ ；
通过给边赋予全局唯一标识 edge_id 优雅地区分了重边与反向边；
使用迭代显式栈规避了深度递归栈溢出的工程隐患。