「一本通 3.6 例 1」分离的路径

形式化题目

给定一个包含 $F$ 个顶点、 $R$ 条边的无向连通图（可能存在重边）。

求最少添加多少条无向边，使得整张图变成边双连通图（即任意两点之间至少存在两条没有公共边的路径，换言之，图中不存在割边/桥）。

正解

思路

1. 问题等价转化与缩点

“任意两个草场之间至少有两条边不相交的路径”在图论中等价于整张图不存在桥（割边），即图是边双连通的。

原图中若已经存在一些边双连通分量（ $e\text{-DCC}$ ），这些分量内部任意两点间已经满足存在至少两条分离路径。因此：

我们可以用 Tarjan 算法找出原图所有的边双连通分量，并将每个分量缩成一个点。
缩点后，只有原图的“桥”连接不同的双连通分量。因为原图是连通图，缩点后的新图必然是一棵无向树（若原图本身就是边双连通图，则缩点后只有一个点）。

2. 树上最少加边问题

现在问题转化为：在一棵树上最少添加多少条边，能使其变为一个边双连通图？

树上的所有边都是桥。当我们在树上任意两点 $u, v$ 之间添加一条新边时，会将 $u$ 到 $v$ 的树上路径覆盖在一个简单环中，这条路径上的所有桥边都会被消除。
考察树上的叶子节点（度数为 $1$ 的节点）：连接叶子节点与父节点的边是桥，若没有任何新边以该叶子节点为端点，则这条边永远不可能被包含在环中。因此，每个叶子节点必须至少作为一条新边的端点。
一条新边连接两个节点，最多只能同时为两个叶子节点提供覆盖。
设缩点后树中度数为 $1$ 的叶子节点数量为 $L$ ：
- 每条新边最多减少 $2$ 个度为 $1$ 的节点，因此至少需要 $\lceil L / 2 \rceil = \lfloor (L + 1) / 2 \rfloor$ 条新边。
- 构造性证明表明：按 DFS 序将叶子节点排列，令前半部分叶子与后半部分叶子两两跨树根/重心相连，恰好只需 $\lceil L / 2 \rceil$ 条边即可覆盖树上的所有边。

综上，算法流程为：

Tarjan 算法求出所有边双连通分量，注意使用边的编号记录反向边以正确处理重边；
统计缩点后各分量在新图中的度数；
统计度数为 $1$ 的分量个数 $L$ ，答案即为 $\lfloor (L + 1) / 2 \rfloor$ 。

可视化解析

以样例输入为例：

text

原图中存在环 $\{2, 3, 4, 5\}$ ，它们属于同一个边双连通分量。

graph TD
    subgraph 原图连通结构
        1((1)) --- 2((2))
        2 --- 3((3))
        3 --- 4((4))
        4 --- 5((5))
        2 --- 5
        5 --- 6((6))
        5 --- 7((7))
    end

进行边双连通分量缩点后：

分量 A: $\{1\}$ ，度数为 1（叶子）
分量 B: $\{2, 3, 4, 5\}$ ，度数为 3（内部节点）
分量 C: $\{6\}$ ，度数为 1（叶子）
分量 D: $\{7\}$ ，度数为 1（叶子）

graph TD
    subgraph 缩点后的树结构
        A["{1} (度数 1)"] --- B["{2, 3, 4, 5} (度数 3)"]
        C["{6} (度数 1)"] --- B
        D["{7} (度数 1)"] --- B
    end

度数为 $1$ 的叶子节点共有 $L = 3$ 个（ $\{1\}, \{6\}, \{7\}$ ），最少需要添加的新边数为：

\lfloor (3 + 1) / 2 \rfloor = 2

样例中连接 $(1, 6)$ 与 $(4, 7)$ （即分量 A 与 C、B 与 D），即可消除所有的桥。

代码

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#!/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 15:55
# update_at: 2026-09-30 15:55

import sys
from collections.abc import Iterator


def find_bridge_components(n: int, edges: list[tuple[int, int]]) -> list[int]:
    """通过 Tarjan 算法求出无向图各顶点所属的边双连通分量 (e-DCC) 编号。"""
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for eid, (u, v) in enumerate(edges):
        adj[u].append((v, eid))
        adj[v].append((u, eid))

    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    dcc = [0] * (n + 1)
    clock = 0
    dcc_cnt = 0
    stack: list[int] = []

    # 显式栈模拟 Tarjan DFS 遍历，避免递归深度受限
    # 栈元素: (当前节点 u, 遍历边生成器/游标, 来向边 id)
    for start in range(1, n + 1):
        if dfn[start]:
            continue
        call_stack: list[tuple[int, Iterator[tuple[int, int]], int]] = []
        clock += 1
        dfn[start] = low[start] = clock
        stack.append(start)
        call_stack.append((start, iter(adj[start]), -1))

        while call_stack:
            u, it, in_eid = call_stack[-1]
            try:
                v, eid = next(it)
                if eid == in_eid:
                    continue
                if not dfn[v]:
                    clock += 1
                    dfn[v] = low[v] = clock
                    stack.append(v)
                    call_stack.append((v, iter(adj[v]), eid))
                else:
                    low[u] = min(low[u], dfn[v])
            except StopIteration:
                call_stack.pop()
                if call_stack:
                    p = call_stack[-1][0]
                    low[p] = min(low[p], low[u])
                if dfn[u] == low[u]:
                    dcc_cnt += 1
                    while True:
                        node = stack.pop()
                        dcc[node] = dcc_cnt
                        if node == u:
                            break

    return dcc


def count_leaf_components(dcc: list[int], edges: list[tuple[int, int]]) -> int:
    """统计边双缩点后度数为 1 的树叶子节点数量。"""
    dcc_cnt = max(dcc) if dcc else 0
    degree = [0] * (dcc_cnt + 1)
    for u, v in edges:
        if dcc[u] != dcc[v]:
            degree[dcc[u]] += 1
            degree[dcc[v]] += 1
    return sum(1 for d in degree[1:] if d == 1)


def solve() -> None:
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = iter(input_data)
    n = int(next(it))
    m = int(next(it))
    edges = [(int(next(it)), int(next(it))) for _ in range(m)]

    dcc = find_bridge_components(n, edges)
    leaf_cnt = count_leaf_components(dcc, edges)
    print((leaf_cnt + 1) // 2)


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/**
 * 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 05:57
 * update_at: 2026-10-05 05:57
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;   // 草场数上限
const int MAXM = 20005;  // 边数上限（2 * R）

typedef long long ll;

int n, m;
int head[MAXN], nxt[MAXM], to[MAXM], edge_cnt = 1; // 链式前向星，edge_cnt 从 1 开始，2/3、4/5 互为反向边
int dfn[MAXN], low[MAXN], timer_cnt;  // Tarjan 时间戳与 low 值
int dcc[MAXN], dcc_cnt;               // dcc[i] 表示点 i 所属的边双连通分量编号
int stk[MAXN], top_stk;               // Tarjan 栈，保存当前搜索树上的点
int deg[MAXN];                        // 缩点后每个分量的度数

// 加一条无向边（成对存，反向边编号 = 边编号 xor 1）。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// Tarjan 求边双连通分量：in_edge 记录来向边的编号，这样重边不会被当成反向边跳过。
void dfs(int u, int in_edge) {
    timer_cnt++;
    dfn[u] = low[u] = timer_cnt;
    top_stk++;
    stk[top_stk] = u; // 点进栈，出栈时机是该点所属分量被确定

    for (int i = head[u]; i != 0; i = nxt[i]) {
        int v = to[i];
        if (dfn[v] == 0) { // 树边
            dfs(v, i);
            if (low[v] < low[u]) low[u] = low[v];
        }
        else if (i != (in_edge ^ 1)) { // 非树边且不是来向边的反向边（允许重边）
            if (dfn[v] < low[u]) low[u] = dfn[v];
        }
    }

    // low[u] == dfn[u] 说明 u 是该边双连通分量中最早的点，弹出整个分量
    if (low[u] == dfn[u]) {
        dcc_cnt++;
        while (top_stk > 0) {
            int x = stk[top_stk];
            top_stk--;
            dcc[x] = dcc_cnt;
            if (x == u) break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    dfs(1, 0); // 题目保证原图连通，从 1 号点出发一次即可

    // 枚举每条边，统计缩点后（分量树）各点的度数
    for (int i = 2; i <= edge_cnt; i += 2) {
        int u = to[i ^ 1], v = to[i]; // 第 i 条边的两个端点
        if (dcc[u] != dcc[v]) {
            deg[dcc[u]]++;
            deg[dcc[v]]++;
        }
    }

    // 度数为 1 的分量就是缩点后树上的叶子，设叶子数为 L，答案为 (L + 1) / 2
    int leaf = 0;
    for (int i = 1; i <= dcc_cnt; i++) {
        if (deg[i] == 1) leaf++;
    }
    cout << (leaf + 1) / 2 << endl;

    return 0;
}

复杂度

时间复杂度： $O(F + R)$ 。Tarjan 算法对每个点和每条边访问常数次，缩点及度数统计遍历所有边一次，总时间复杂度与点数和边数呈线性关系。
空间复杂度： $O(F + R)$ 。主要为邻接表、Tarjan 辅助数组（dfn, low, dcc）及递归调用栈的开销。

总结

本题是边双连通分量与树上性质结合的经典模型：

要求在图中加边消除所有的桥使之边双连通，标准套路是求出所有边双连通分量并缩点，将原图转化为一棵树。
树上加边消桥的充要下界由叶子节点决定：连接 $L$ 个叶子节点至少需要 $\lceil L / 2 \rceil$ 条边，直接统计叶子数即可得出答案。

「一本通 3.6 例 1」分离的路径

目录

形式化题目

正解

思路

1. 问题等价转化与缩点

2. 树上最少加边问题

可视化解析

代码

复杂度

总结