GESP 题解库 / 7 级题解 / [GESP202509 七级] 连通图 · 第 6 / 24 题
GESP202509 七级 · P14077 · 简单

连通图

求最少加入多少条边,使整张无向图连通。

📊
n, m ≤ 10⁵
数据规模
🔗
连通块数 − 1
答案公式
⚡
O((n + m) α(n))
时间复杂度
🎯
并查集
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定一张包含 n 个结点与 m 条边的无向图,结点以 1, 2, …, n 编号,第 i 条边连接结点 uᵢ 与结点 vᵢ。如果从一个结点经过若干条边可以到达另一个结点,则称这两个结点是连通的。

你需要向图中加入若干条边,使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。

注意:给出的图中可能包含重边与自环。

💡
人话翻译:先把图里已有的"连通块"数出来(设为 k 个)。答案就是 k − 1。
为什么?每加入一条边,最多只能把两个连通块并成一个,所以把 k 个块并成 1 个至少要 k − 1 条;
而"把第 2 个块连到第 1 个、第 3 个块连到第 1 个……"这个构造恰好用 k − 1 条就能连通,所以下界可以达到,答案就是 k − 1。
自环(uᵢ = vᵢ)和重边都不会改变连通块个数,可以放心忽略。

🔍 关键词提取

并查集连通块计数重边与自环最少加边下界与构造

已知条件

项目说明
输入第一行 n、m;随后 m 行每行 uᵢ、vᵢ
输出使得全图连通所需加入的最少边数
数据范围1 ≤ n ≤ 10⁵,1 ≤ m ≤ 10⁵
图的类型无向图,可能含重边与自环
规模风险n = 10⁵ 时深递归的 DFS 有爆栈风险
40% 部分分1 ≤ n, m ≤ 100

需要解决的问题

02
思维导图
整理解题思路的全貌
🔗 答案 = 连通块个数 − 1
🧠 核心结论
加一条边最多合并两个连通块
所以至少要 (块数 − 1) 条
把各块顺次"串"起来即可达到下界
下界可构造 ⟹ 答案就是块数 − 1
📐 做法
初始化:每个结点各成一个集合
读入每条边,合并它的两个端点
统计不同的集合个数 k
答案 = k − 1
🛡️ 重边与自环
自环 u = v:两端同点,合并无效
重边:重复合并同一对集合
两者都不改变连通块个数
并查集天然把它们"吃掉",无需特判
⚠️ 易错点
答案写成"块数"忘了减 1
DFS 深递归在链形图上爆栈
统计块数时把下标 0 的哨兵也算进去
n = 1 时多加了 1 条边
03
样例手算推导
两个样例的并查集合并过程

🧮 样例 1:4 个结点 4 条边,答案 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
逐条合并的过程

初始:{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

2
答案的意义

块数已经是 1,图本来就连通

一条边都不用加

输出 1 − 1 = 0

✅ 输出 0

🔑
注意第 3 条边 3-1:它连接的两个点已经在同一个集合里了,所以合并操作什么都不做。
这正是"判环"的原理——若一条边的两个端点已同集合,说明加入它会形成环。Kruskal 最小生成树就是靠这一点判断"这条边要不要用"。

🧮 样例 2:6 个结点 4 条边,答案 2

输入: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 ✓

1
三个块分别是谁

块 A:{1, 2, 3}(被三条边连成三角形)

块 B:{4}(孤立结点,没有任何边)

块 C:{5, 6}(被一条边连起来)

块数 k = 3

✅ k = 3

2
两条边怎么加

第 1 条:连接块 A 与块 B,比如加边 3-4

此时 {1,2,3,4} 与 {5,6} 共 2 个块

第 2 条:连接剩余两块,比如加边 4-5

此时全部点属于同一块,连通完成

✅ 2 条,且不可能更少

⚠️
为什么不可能少于 2 条?初始有 3 个块,而一条边只能把 2 个块变成 1 个,也就是每加一条边块数最多减 1。要把 3 个块减到 1 个,至少要减 2 次,也就是至少 2 条边。
这个"下界 + 构造"的论证方式,是很多"最少操作次数"类题目的标准答法。
04
解法对比
并查集 vs 建图后 BFS/DFS 数连通块

⚔️ 解法对比

🟢 并查集(推荐) 推荐

初始化每个点各成集合,逐条边合并,最后数剩余集合个数

  • 时间 O((n + m) α(n)),α(n) ≤ 4
  • 只需 两个长度 n + 1 的数组
  • 代码约 15 行
  • 不建图、不递归
💡
并查集在这里特别合适:本题只关心"哪些点连在一起",不关心具体怎么连,所以不需要把图完整存下来。
自环与重边也因此自动免疫——它们对"集合划分"没有任何影响。

🟠 建图后 BFS / DFS 染色

建邻接表,对每个未访问点启动一次遍历,计数启动次数

  • 时间 O(n + m)
  • 同样正确
  • 要建邻接表,空间 O(n + m)
  • 递归 DFS 在 n = 10⁵ 的链上可能爆栈
⚠️
两种都满分,看习惯选:DFS/BFS 更直观("染色的次数就是块数");并查集代码更短、常数更小、不用存图。
但如果要处理"边是动态加入的",并查集就是唯一选择——BFS/DFS 无法增量维护。

📈 性能对比

方案复杂度n = m = 10⁵ 时的表现
并查集O((n + m) α(n))≈ 2 × 10⁵ 次操作 ✅
BFS / DFS 染色O(n + m)同样可行,但要多存一张图
逐对点判断连通O(n²(n + m))❌ 完全不可行
05
算法流程图
并查集合并所有边,答案 = 连通块数 − 1
开始读入 n, m,初始化并查集:每个结点各成一个集合for 每条边 (u, v):尝试合并 u 与 v 所在的集合merge(u, v) 真的把两个集合合起来了吗?是 ✓连通块个数减 1(它连接了两个不同的块)否 ✗什么都不做(同集合 / 自环)ans = 连通块个数 − 1输出 ans处理下一条边
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔗 最少需要加入几条边

第一行输入 n 和 m,随后 m 行每行一条边的两个端点(允许重边与自环)。程序用并查集逐步合并并统计连通块个数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(并查集 + 按大小合并)

#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;
}
🔑
为什么"块数 − 1"就是答案?
下界:一条边只有两个端点,所以它最多把 2 个连通块并成 1 个,块数一次最多减 1。从 k 个块减到 1 个,至少要 k − 1 步。
构造:任选一个块当"中心",其余 k − 1 个块各出一条边与中心相连——正好 k − 1 条边就把全部点连通了。
下界能达到,所以最小条数就是 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⁵ 会栈溢出。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 4
1 2
2 3
3 1
1 4
0题面样例 1:本来就连通,一块都不用加
6 4
1 2
2 3
3 1
6 5
2题面样例 2:3 个连通块 → 3 − 1 = 2
1 1
1 1
0n = 1 的边界:唯一的点自己就连通,答案为 0
3 3
1 1
2 2
3 3
2三条自环全都无效:仍是 3 个块 → 需要 2 条
3 3
1 2
1 2
2 3
0重边无害:1-2 出现两次也只是一个块
4 2
1 1
2 2
3两条自环 + 两个孤立点:4 个块 → 需要 3 条
✅
自查清单:① 最终输出的是 comp − 1 吗?② 并查集同时做了路径压缩与按大小合并吗?③ n = 1 时结果对吗?④ 统计集合个数时下标范围是 1 ~ n 吗?

🚨 易错点清单

⚠️
忘记减 1:答案是"连通块个数 − 1";图本来就连通时应输出 0。
⚠️
递归爆栈:n = 10⁵ 的链形图上递归 DFS 深度达 10⁵,要改用 BFS 或迭代写法。
⚠️
统计范围出错:数连通块时只在 1 ~ n 里统计,别把下标 0 的哨兵算进去。
⚠️
被重边自环干扰:自环 u = v 不合并任何集合,重边也不增加块数,无需特判。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + m) α(n))
空间复杂度
O(n)
n, m 最大
10⁵
运算量
约 2 × 10⁵ 次查询/合并

时间怎么算的?

空间都用在哪?

只需要两个长度为 n + 1 的数组 fa 与 sz,连图都不用存,所以内存占用远小于"建邻接表"的写法。

✅ 约 20 万次近似常数级的操作,瞬间完成。而且这份并查集代码可以原封不动地用在 Kruskal 最小生成树、判环、种类并查集等一大类题目里。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// —— 并查集模板(路径压缩 + 按大小合并)——
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 最小生成树,并查集代码可以一字不改地复用。
而本题相当于把每条边的代价都看成 1,于是"累计代价最小"就退化成"最少加几条",答案自然就是连通块个数减 1。看懂这一点,你就顺手学会了一道更难的题。)