求最少加入多少条边,使整张无向图连通。
给定一张包含 n 个结点与 m 条边的无向图,结点以 1, 2, …, n 编号,第 i 条边连接结点 uᵢ 与结点 vᵢ。如果从一个结点经过若干条边可以到达另一个结点,则称这两个结点是连通的。
你需要向图中加入若干条边,使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。
注意:给出的图中可能包含重边与自环。
并查集连通块计数重边与自环最少加边下界与构造
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 m 行每行 uᵢ、vᵢ |
| 输出 | 使得全图连通所需加入的最少边数 |
| 数据范围 | 1 ≤ n ≤ 10⁵,1 ≤ m ≤ 10⁵ |
| 图的类型 | 无向图,可能含重边与自环 |
| 规模风险 | n = 10⁵ 时深递归的 DFS 有爆栈风险 |
| 40% 部分分 | 1 ≤ n, m ≤ 100 |
1 − 1 = 0输入:4 4,边为 1-2、2-3、3-1、1-4。前三条边把 1、2、3 连成一个三角形,第 4 条边把结点 4 也拉了进来。
| 处理的边 | u 所在集合 | v 所在集合 | 是否合并 | 合并后连通块数 |
|---|---|---|---|---|
| 1-2 | {1} | {2} | 是 | 3 |
| 2-3 | {1,2} | {3} | 是 | 2 |
| 3-1 | {1,2,3} | {1,2,3} | 否(已同块) | 2 |
| 1-4 | {1,2,3} | {4} | 是 | 1 |
连通块数 = 1 → 答案 1 − 1 = 0 ✓
初始:{1} {2} {3} {4},块数 4
边 1-2:合并 → {1,2} {3} {4},块数 3
边 2-3:合并 → {1,2,3} {4},块数 2
边 3-1:3 与 1 已同块,跳过,块数仍为 2
边 1-4:合并 → {1,2,3,4},块数 1
✅ 块数 = 1
块数已经是 1,图本来就连通
一条边都不用加
输出 1 − 1 = 0
✅ 输出 0
3-1:它连接的两个点已经在同一个集合里了,所以合并操作什么都不做。输入:6 4,边为 1-2、2-3、3-1、6-5。前三条边把 {1,2,3} 连成一块,第 4 条边把 {5,6} 连成一块,而结点 4 谁也不连。
| 处理的边 | 是否合并 | 连通块情况 | 连通块数 |
|---|---|---|---|
| 1-2 | 是 | {1,2} {3} {4} {5} {6} | 5 |
| 2-3 | 是 | {1,2,3} {4} {5} {6} | 4 |
| 3-1 | 否(已同块) | {1,2,3} {4} {5} {6} | 4 |
| 6-5 | 是 | {1,2,3} {4} {5,6} | 3 |
连通块数 = 3 → 答案 3 − 1 = 2 ✓
块 A:{1, 2, 3}(被三条边连成三角形)
块 B:{4}(孤立结点,没有任何边)
块 C:{5, 6}(被一条边连起来)
块数 k = 3
✅ k = 3
第 1 条:连接块 A 与块 B,比如加边 3-4
此时 {1,2,3,4} 与 {5,6} 共 2 个块
第 2 条:连接剩余两块,比如加边 4-5
此时全部点属于同一块,连通完成
✅ 2 条,且不可能更少
初始化每个点各成集合,逐条边合并,最后数剩余集合个数
建邻接表,对每个未访问点启动一次遍历,计数启动次数
| 方案 | 复杂度 | n = m = 10⁵ 时的表现 |
|---|---|---|
| 并查集 | O((n + m) α(n)) | ≈ 2 × 10⁵ 次操作 ✅ |
| BFS / DFS 染色 | O(n + m) | 同样可行,但要多存一张图 |
| 逐对点判断连通 | O(n²(n + m)) | ❌ 完全不可行 |
第一行输入 n 和 m,随后 m 行每行一条边的两个端点(允许重边与自环)。程序用并查集逐步合并并统计连通块个数。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int fa[MAXN]; // 父亲 int sz[MAXN]; // 集合大小(用于按大小合并) int find(int x) { // 路径压缩 return fa[x] == x ? x : fa[x] = find(fa[x]); } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { // 每个结点各成一个集合 fa[i] = i; sz[i] = 1; } int comp = n; // 连通块个数:初始为 n for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); int a = find(u), b = find(v); if (a != b) { // 属于不同集合 → 这次合并有效 if (sz[a] < sz[b]) swap(a, b); // 小集合并到大集合 fa[b] = a; sz[a] += sz[b]; comp--; // 两个块并成一个,块数减 1 } // 自环(u == v)与重边都会落到这里,但 a == b,什么都不做 } printf("%d\n", comp - 1); // 答案 = 连通块个数 − 1 return 0; }
k − 1 步。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; } | 初始化 | 每个结点自成一个连通块,共 n 块 |
if (a != b) { fa[b] = a; comp--; } | 合并并计数 | 只有真的合并了,块数才减 1 |
if (sz[a] < sz[b]) swap(a, b); | 按大小合并 | 让小树挂到大树上,树高保持 O(log n),递归不爆栈 |
return fa[x] == x ? x : fa[x] = find(fa[x]); | 路径压缩 | 顺手把路径上的点直接挂到根,后续查询更快 |
printf("%d
", comp - 1); | 输出 | 答案是块数减 1,不是块数本身 |
comp 忘记减 1(连通图的答案应是 0);② 只写路径压缩、不写按大小合并,在精心构造的数据上树高可能到 O(n),递归的 find 会爆栈——两者一起用才是稳的写法;③ 统计块数时循环写成 0 ~ n,把下标 0 那个没用到的哨兵也算成一个块;④ 用 DFS 数块时没注意n = 10⁵ 的链形图,递归深度 10⁵ 会栈溢出。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 4 | 0 | 题面样例 1:本来就连通,一块都不用加 |
6 4 | 2 | 题面样例 2:3 个连通块 → 3 − 1 = 2 |
1 1 | 0 | n = 1 的边界:唯一的点自己就连通,答案为 0 |
3 3 | 2 | 三条自环全都无效:仍是 3 个块 → 需要 2 条 |
3 3 | 0 | 重边无害:1-2 出现两次也只是一个块 |
4 2 | 3 | 两条自环 + 两个孤立点:4 个块 → 需要 3 条 |
comp − 1 吗?② 并查集同时做了路径压缩与按大小合并吗?③ n = 1 时结果对吗?④ 统计集合个数时下标范围是 1 ~ n 吗?n = 10⁵ 的链形图上递归 DFS 深度达 10⁵,要改用 BFS 或迭代写法。1 ~ n 里统计,别把下标 0 的哨兵算进去。u = v 不合并任何集合,重边也不增加块数,无需特判。只需要两个长度为 n + 1 的数组 fa 与 sz,连图都不用存,所以内存占用远小于"建邻接表"的写法。
✅ 约 20 万次近似常数级的操作,瞬间完成。而且这份并查集代码可以原封不动地用在 Kruskal 最小生成树、判环、种类并查集等一大类题目里。
// —— 并查集模板(路径压缩 + 按大小合并)—— int fa[MAXN], sz[MAXN]; void init(int n) { for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; } } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } bool uni(int a, int b) { a = find(a); b = find(b); if (a == b) return false; // 已同集合(这条边会成环) if (sz[a] < sz[b]) swap(a, b); fa[b] = a; sz[a] += sz[b]; return true; // 真正合并成功 } // —— 本题用法 —— // comp = n; 每成功 uni(u, v) 一次就 comp--; // 答案 = comp - 1 // —— 变式:Kruskal 最小生成树 —— // 把所有边按权值升序排序,依次 uni(); // 成功一次就把权值累加并计数,直到凑够 n - 1 条 → 总权值即 MST 代价 // —— 变式:判断无向图是否有环 —— // 任意一条边 uni(u, v) 返回 false ,说明 u 与 v 已连通 ⟹ 存在环
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 并查集(压缩 + 按大小合并) | 维护"哪些点在一起" | Kruskal、判环、动态连通性 |
| 连通块个数 | 块数 − 1 即最少加边数 | 最少合并次数、最少修路条数类问题 |
| 重边与自环免疫 | u = v 时 find 相同,自动跳过 | 处理含脏数据的输入 |
| 下界 + 构造的论证 | 每步最多减 1 个块,且能做到 | 一切"最少操作次数"的严格证明 |
wᵢ,要求让图连通且总代价最小",该怎么做?(提示:思路几乎不变——把所有候选边按代价升序排序,依次尝试合并:能合并就加进来并累加代价,合并成功 n − 1 次后停止。这正是著名的 Kruskal 最小生成树,并查集代码可以一字不改地复用。