Skip to content

并查集

维护不相交集合,支持快速合并与查询连通性。

Updated View as Markdown

有一类问题反复出现:不断把两个元素归成一类,同时问两个元素是不是同一类。朋友的朋友也是朋友、两个城市通不通路、两个点连不连通,都是这个形式。

并查集(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 条边也够了——每加一条边就能合并两个连通块。

所以算法就是三步:

  1. 初始化 fa[i] = i,用 cnt = n 记录「当前连通块个数」;
  2. 每读入一条边 (u, v),如果 find(u) != find(v),就合并并把 cnt--;
  3. 最后输出 cnt - 1。

几个值得注意的地方:

  1. 不需要存图。并查集边读边合并,空间只要 O(n)。而 DFS/BFS 要建邻接表,空间 O(n + m)。这是并查集在这类「只问连通性」题目上的优势。
  2. 重边与自环自动被忽略。自环 (u, u) 时 find(u) == find(u),不合并;重边第二次读到时已经连通,也不合并。不需要写任何特判。
  3. cnt 的维护方式。也可以用「最后统计 find(i) == i 的个数」,但边合并边减更快,而且避免了对每个点再调一次 find。
  4. n = 1:cnt = 1,输出 0,正确。
  5. 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)。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close