最短路回答“怎样以最小代价走到那里”，连通性则先问“能不能走到”。在 Dijkstra 和 0-1 BFS 之后，25D 提供另一条图论进阶路线：不计算距离，只维护哪些顶点属于同一个集合，并输出最少的路网改造操作。

这道题的关键不只是会写并查集。还要证明：记录下来的多余边为什么可以逐条拆除，数量为什么恰好够用，以及新建道路怎样保证连接不同区域。

1. 官方信息与目标

25D · Roads not only in Berland 官方题目 于 2026-09-09 核对：难度 1900，标签为 dsu、graphs、trees，时间限制 2 秒，内存限制 256 MB。

原创概括：给定 n 个顶点和恰好 n−1 条无向边。每次必须关闭一条现有道路，并立刻修建一条新道路。让全部城市连通，要求操作次数最少，并输出每次关闭、新建道路的端点。

官方条件 为什么重要
2 ≤ n ≤ 1000 可以用小数组维护集合；不需要复杂图存储
恰好 n−1 条边 最终连通时必为树；多余边与连接缺口可以精确配对
无自环、无重边 生成测试也应遵守简单图条件
初始不保证连通 n−1 条边本身不能推出“已经是一棵树”
输出方案，允许任意最优解 验证应检查操作合法性，而非与某份输出逐字比较

2. 先看朴素方法，明确真正缺少的东西

只用 DFS 数出 k 个连通分量，可以得到至少要新建 k−1 条跨分量边。但题目规定建一条必须先拆一条，输出答案数字还不够：从哪里拆，才能不破坏已有连通性？

每次试着删除一条边，再跑一遍 DFS 判断是否断开，是一个直观办法。本题规模下不必武断认为 O(n²) 一定超时，但重复检查掩盖了更有用的结构：我们可以一次扫描就选出每个分量必须保留的树边，把其余边全部记为可用资源。

一次 DFS 建生成森林同样可以实现线性解法。本文选择并查集，是为了练习“逐条加入边时维护连通性”，为之后的 Kruskal 做准备，而不是声称 DFS 无法解决本题。

3. 并查集保存的不是道路

并查集（Disjoint Set Union，DSU）维护集合划分：

  • find(v)：返回 v 所属集合的代表；
  • unite(a,b)：若代表不同，合并两集合并返回成功；否则返回失败；
  • parent[v]：数据结构内部的父指针，不表示图中存在对应道路。

最初每个顶点单独成集。逐条读取边 (a,b)：若能合并，就把它视为保留的森林边；若不能，说明两个端点已经由之前保留的边连通，它是多余边。

森林不变量： 每次保留的边连接两棵不同的树，因此不会产生环；被拒绝的边两端已经有一条完全由保留边组成的路径。扫描结束后，保留边构成覆盖所有顶点的生成森林，并保留了原图各分量内部的连通性。

4. 为什么多余边恰好有 k−1 条

设原图有 k 个连通分量，分量顶点数为 s₁,…,sₖ。每个分量的生成树需要 sᵢ−1 条边，于是整个森林保留：

1
(s₁−1) + … + (sₖ−1) = n−k 条边

原图有 n−1 条边，因此被拒绝的边数量为：

1
(n−1) − (n−k) = k−1

这一等式解释了“环”和“不连通”为何会同时出现：在总边数固定为 n−1 时，一个区域多绕出的连接，正对应另一些区域缺少的连接。

注意条件不能省略。若一般图只有 m 条边，多余边数量变成 m−n+k，不一定等于 k−1；当 m<n−1 时，保持边数的替换操作根本不可能让图连通。

5. 从计数到可执行方案

为每个原始分量选一个代表顶点 r₀,r₁,…,rₖ₋₁。把多余边依次改成：

1
2
3
4
r₀—r₁
r₀—r₂
…
r₀—rₖ₋₁

这相当于在“分量图”上建一棵星形树。

每次拆边安全： 所有保留森林边始终不被拆掉。任意一条记录的多余边，其两端仍有森林路径相连，所以即使其他多余边早已拆除，删除当前边也不会把分量拆开。不能只说“这条边原来在环上”，还要说明支撑这个环的替代路径一直保留着。

每次建边合法： 第 i 次连接的是已经汇合到中心的区域与尚未连接的原始分量 i。它们之间不可能已有道路，否则原始分量就不独立；先前操作也没有连接这个分量。因此新边既不是自环，也不是重边，而且恰好让分量数减一。

操作数最优： 删除一条边不可能减少连通分量数，新建一条边最多减少一个。从 k 个分量变成一个，至少需要 k−1 次操作；上述构造恰好使用 k−1 次，所以达到下界。

代码只需要输出这张计划，不必在 DSU 中模拟删边。构造时的代表是固定顶点编号，即使实际路网已经合并，它们仍是合法端点。

6. 手工演算：两个三角形与一个孤立点

自拟输入为 n=7，按顺序读入六条边：1-2, 2-3, 3-1, 4-5, 5-6, 6-4，顶点 7 孤立。

读入边 处理结果 扫描后的分量数
1—2 保留，合并 6
2—3 保留，合并 5
3—1 多余边，记录 5
4—5 保留，合并 4
5—6 保留，合并 3
6—4 多余边，记录 3

可选择代表 1、4、7，输出下面的计划：

1
2
3
2
3 1 1 4
6 4 1 7
操作 拆后仍保留的替代路径 新建道路 操作后分量数
拆 3—1 3—2—1 1—4 2
拆 6—4 6—5—4 1—7 1

最终仍为六条边、七个顶点，但已经连通，因此是树。多余边可以来自同一个分量，不要求“一分量对应一条可拆边”。

7. 完整 C++17 实现

采用路径压缩与按集合大小合并。合并时只修改代表的父指针；size 只在代表处有意义。

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
#include <iostream>
#include <vector>
#include <numeric>
#include <utility>
using namespace std;

struct DSU {
    vector<int> parent, size;
    explicit DSU(int n) : parent(n + 1), size(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int v) {
        if (parent[v] != v) parent[v] = find(parent[v]);
        return parent[v];
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    DSU dsu(n);
    vector<pair<int, int>> redundant;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        if (!dsu.unite(a, b)) redundant.emplace_back(a, b);
    }
    vector<int> roots;
    for (int v = 1; v <= n; ++v) {
        if (dsu.find(v) == v) roots.push_back(v);
    }
    cout << roots.size() - 1 << '\n';
    for (int i = 1; i < static_cast<int>(roots.size()); ++i) {
        auto [a, b] = redundant[i - 1];
        cout << a << ' ' << b << ' ' << roots[0] << ' ' << roots[i] << '\n';
    }
    return 0;
}

8. 复杂度与边界检查

扫描 n−1 条边并遍历 n 个顶点，使用路径压缩与按大小合并的 DSU，总时间为 O(n α(n))，空间 O(n)。α 是反阿克曼函数，这里只需把它理解为增长极慢的摊还因子，而不是声称任意一次 find 都严格 O(1)。按大小合并还限制了树高，n≤1000 下递归 find 不会形成千层长链。顶点编号、集合大小和操作计数使用 int 足够。

边界或错误 正确处理
n=2，唯一道路已经连通 输出 0，不访问空的多余边列表
原图本来就是树 k=1，同样无需改路
存在孤立点 初始化必须覆盖所有顶点，不能只记录出现在边上的城市
多个环集中在一个分量 每条被拒绝的边分别记录，不按分量只留一条
用 parent 指针当作要拆的道路 错误；只能拆保存下来的输入边
找到一条环边后随意拆其余边 可能拆掉桥；应始终保护选定森林
试图用普通并查集支持任意删边 它不会自动拆分集合；本题靠离线构造避开删除维护

9. 独立验证：既检查结果，也检查每一步

验证脚本 tests/verify-roads-article.cjs 从本文提取并编译 C++17。参考验证器不使用并查集，而是直接维护边集合并用 BFS 数连通分量。

每一行输出都检查：旧边当前存在、新边端点有效且不重复、拆边没有增加分量数、新建边使分量数减一；最后检查连通、边数仍为 n−1，并且操作数最优。

对 n≤5，还穷举所有可能的最终生成树，求“至少需要替换多少条原边”，独立核验最优值，而不只复用 k−1 公式。再加入随机简单图、两个官方样例、本文手算、千点长链和多环集中于小分量的边界图。

10. 下一步如何接到最小生成树

25D 中边没有权重，输入顺序选出的任意生成森林都能支持构造。Kruskal 会先按权重排序，再用同样的“连接不同集合才保留”规则选边；要说明权重和最小，还需要割性质或交换论证，不能仅凭“没有环”得出最优。

回到 算法练习路径，可以把三种目标分开：BFS/Dijkstra 优化从起点到各点的路程，并查集维护集合是否连通，最小生成树优化连接全部顶点的总边权。它们都处理图，但保存的信息与证明目标不同。