有一类问题反复出现:不断把两个元素归成一类,同时问两个元素是不是同一类。朋友的朋友也是朋友、两个城市通不通路、两个点连不连通,都是这个形式。
并查集(Disjoint Set Union,DSU)专门解决这类问题。它只支持两个操作,但都做到了几乎 O(1)。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| CSP-J/S 提高级 | 2.3.2 集合与森林:并查集 | 全章 |
基本思路
并查集把元素分成若干个不相交的集合。每个集合选一个代表元,用一个数组记下每个元素的「上级」:
int fa[100005]; // fa[i] 表示 i 的父节点- 如果
fa[i] == i,说明 i 是自己这个集合的代表元,也就是根。 - 否则沿着
fa一直往上找,一直找到根为止。
两个元素属于同一个集合,当且仅当它们的根相同。
初始时每个元素各成一个集合,fa[i] = i。
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i;
}查找与路径压缩
find(x) 要找 x 所在集合的根。
int find(int x) {
if (fa[x] == x) return x; // 自己是根
return fa[x] = find(fa[x]); // 递归找根,顺便把沿途节点直接挂到根上
}关键是 return fa[x] = find(fa[x]) 这一句。它不仅找到了根,还把 x 的父节点直接改成根。这个操作叫路径压缩。
为什么重要?如果只是老老实实沿链往上找,树可能退化成一条链,每次查找都是 O(n)。路径压缩之后,第一次找要走的路径,之后几乎所有节点都直接连着根,后续查找接近 O(1)。
合并
把两个集合合并,只需要把其中一个的根接到另一个的根上。
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return; // 已经在一起了
fa[rx] = ry; // 把 rx 的树接到 ry 上
}这样写虽然简单,但如果总是把大树接到小树上,树会越接越高。加一条按大小合并(或按秩合并)的规则就能避免:
int sz[100005]; // sz[i] 只在 i 是根时有意义,表示集合大小
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
sz[i] = 1;
}
}
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (sz[rx] < sz[ry]) swap(rx, ry); // 让 rx 是较大的那个
fa[ry] = rx; // 小的接到大的上
sz[rx] += sz[ry];
}路径压缩和按大小合并一起用,单次操作的均摊复杂度是 O(\alpha(n)),其中 \alpha 是反阿克曼函数。这个函数增长极慢,在实际数据规模下不会超过 5,所以可以直接当作 O(1)。
典型应用
判断连通性
给你一些「A 和 B 是朋友」的关系,问 C 和 D 是不是朋友。
for (每个关系 a b) unite(a, b);
if (find(c) == find(d)) cout << "是" << endl;
else cout << "不是" << endl;统计连通块个数
合并完所有关系后,数一数有多少个节点满足 find(i) == i。
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (find(i) == i) cnt++;
}
cout << cnt << endl;判断无向图是否有环
遍历每一条边,如果两个端点已经在同一个集合里,说明这条边会成环。
bool hasCycle = false;
for (每条边 u v) {
if (find(u) == find(v)) hasCycle = true;
else unite(u, v);
}Kruskal 最小生成树
Kruskal 算法的核心就是并查集:按边权从小到大排序,依次尝试加入每条边,如果两个端点不连通就加入,否则跳过。判断连通性靠的就是 find。
带权并查集
有时除了「是否同类」,还要维护两个元素之间的相对关系,比如「比对方多多少」。这时给 fa 配上另一个数组记录到父节点的权值,find 时顺便把权值累加,叫带权并查集。属于提高级内容,遇到具体题目再学。
复杂度
| 实现方式 | 单次操作 |
|---|---|
| 朴素 | O(n) |
| 只有路径压缩 | 均摊 O(\log n) |
| 只有按秩合并 | O(\log n) |
| 两者都用 | 均摊 O(\alpha(n)),实际可视为 O(1) |
常见易错点
- 忘记初始化
fa[i] = i,find会跑到奇怪的地方。 - 合并时写
fa[x] = y,直接接了两个具体节点。必须接两个根:fa[find(x)] = find(y)。 - 路径压缩写成了
find(fa[x])但没有赋值回去,压缩就失效了。 - 用
sz数组时只在根节点上维护,合并后旧根的sz就不再有意义。 - 递归版
find在链特别长时可能爆栈,可以改成循环。 - 并查集只能合并,不能拆分。要支持删除就得用别的结构。
- 合并时忘了路径压缩。
fa[a] = b里的a、b必须是find的结果,直接写fa[u] = v会挂错层级。 - 判环时先合并再判断。必须先判断
find(u) == find(v),再决定是否合并;顺序反了就永远判不出环。 - 用并查集判有向图的环。并查集只适用于无向图,有向图要用拓扑排序或 DFS 状态标记。
- 统计连通块时重复调用
find。边合并边用cnt--维护更快,也能避免漏改。
练习
练习 1:连通图(最少加几条边)
在线评测练习:P1110 连通图
GESP C++ 2025.09 · 七级题 1
题目描述
给定一张包含 n 个结点与 m 条边的无向图。如果从一个结点经过若干条边可以到达另一个结点,则称这两个结点是连通的。
你需要向图中加入若干条边,使得图中任意两个结点都是连通的。求最少需要加入的边的条数。
注意给出的图中可能包含重边与自环。
输入格式
第一行两个正整数 n、m。接下来 m 行,每行两个正整数 u_i、v_i。
输出格式
输出一行一个整数,表示最少需要加入的边的数量。
输入输出样例
输入
4 4
1 2
2 3
3 1
1 4输出
0输入
6 4
1 2
2 3
3 1
6 5输出
2数据范围
1 \le n \le 10^5,1 \le m \le 10^5。
题目分析
这道题把并查集的「数连通块」用到了极致,而且比 DFS/BFS 更简洁——不需要建图,边读边合并就行。
核心结论:把 s 个连通块连成一整块,最少需要 s - 1 条边。
为什么?把每个连通块压成一个大点,现在有 s 个大点、0 条边,要让它们连通至少需要 s - 1 条边(生成树);而 s - 1 条边也够了——每加一条边就能合并两个连通块。
所以算法就是三步:
- 初始化
fa[i] = i,用cnt = n记录「当前连通块个数」; - 每读入一条边
(u, v),如果find(u) != find(v),就合并并把cnt--; - 最后输出
cnt - 1。
几个值得注意的地方:
- 不需要存图。并查集边读边合并,空间只要
O(n)。而 DFS/BFS 要建邻接表,空间O(n + m)。这是并查集在这类「只问连通性」题目上的优势。 - 重边与自环自动被忽略。自环
(u, u)时find(u) == find(u),不合并;重边第二次读到时已经连通,也不合并。不需要写任何特判。 cnt的维护方式。也可以用「最后统计find(i) == i的个数」,但边合并边减更快,而且避免了对每个点再调一次find。n = 1:cnt = 1,输出 0,正确。m = 0:cnt = n,输出n - 1,正确。
参考代码
练习 2:无向图判环
题目描述
给定一张 n 个顶点、m 条边的无向图(无自环、无重边),判断它是否包含环。
输入格式
第一行两个整数 n、m;接下来 m 行,每行两个整数 u、v。
输出格式
包含环输出 YES,否则输出 NO。
输入输出样例
输入
4 3
1 2
2 3
3 1输出
YES输入
4 3
1 2
2 3
3 4输出
NO数据范围
1 \le n, m \le 10^5。
题目分析
这是并查集判环的标准写法,比 DFS 版本更短,而且不需要建图、不需要记录父节点。
判据极其简洁:按顺序处理每条边 (u, v)——
- 如果
find(u) != find(v):两点还不连通,这条边是「有用的」,合并它们; - 如果
find(u) == find(v):两点已经连通了,再加这条边必然成环。
为什么这个判据一定对? 因为无向图的每条边连接两个点。如果它们已经在同一棵「合并树」里,说明之前已经有一条路径连通它们,这条新边就与那条路径构成一个环。
和 DFS 版本的对比(见「搜索算法」章节的练习):
| 做法 | 是否需要建图 | 是否需要记父节点 | 代码长度 |
|---|---|---|---|
| DFS | 需要邻接表 | 需要传 parent 排除回头边 |
较长 |
| 并查集 | 不需要 | 不需要 | 极短 |
但两者有一个重要区别:并查集判环只能判「有没有环」,判不了「环在哪里」;而且只能用于无向图(有向图判环要用拓扑排序或 DFS 的「在栈中」标记)。
题目特意说「无自环、无重边」,是为了避免歧义——如果有自环 (u,u),按上面的逻辑会立刻判定成环(find(u)==find(u)),这也符合直觉;有重边时两条相同的边也会构成一个 2-元环。所以这个判据在有自环/重边时同样成立,只是题目想让你专注于一般情形。
参考代码
顺带记住一个简单结论:连通的无向图无环 ⟺
m = n - 1(这样的图就是树)。所以如果题目保证图连通,直接用边数和点数比较就能判,连并查集都省了。
小结
- 并查集维护不相交集合,用
find找代表元,用unite合并两个集合。 - 路径压缩把查找路径上的节点直接挂到根上,按大小合并保证树不会太深。
- 两者结合后单次操作是
O(\alpha(n)),可以当成常数。 - 典型应用是判连通、数连通块、判环和 Kruskal 最小生成树。
s个连通块连成一整块,最少需要s - 1条边。- 并查集判无向图有环:处理每条边时,若两端已连通(
find(u) == find(v))就说明成环。 - 只问连通性时并查集比 DFS/BFS 更优:不用建图,边读边合并,空间只要
O(n)。