本课时有配套视频讲解，购买后即可观看（永久有效）
并查集
一、课上练习
编程练习
二、知识总结
✨ 核心思想
并查集（Union-Find / Disjoint Set Union，简称 DSU）是一种用于管理元素分组的数据结构。它支持两种核心操作：
- 查找（Find）：确定某个元素属于哪个集合（通过查找集合的代表元素/根节点）
- 合并（Union）：将两个不同的集合合并为一个集合
并查集的精髓在于用树形结构表示集合，每棵树的根节点作为该集合的代表元素。通过路径压缩和按秩合并两大优化，使得单次操作的均摊时间复杂度接近 $O(\alpha(n))$，其中 $\alpha$ 是反阿克曼函数，增长极其缓慢，实际可视为常数。
✨ 算法原理
基本结构
每个元素维护一个 parent 指针，指向其父节点。根节点的 parent 指向自身。
路径压缩（Path Compression）
在执行 Find 操作时，将查找路径上的所有节点直接挂到根节点下，从而将树的高度压缩为接近 1。这是一种"懒惰"策略——只在查询时顺便优化结构。
按秩合并（Union by Rank）
合并两棵树时，将秩（rank）较小的树挂到秩较大的树下。秩可以理解为树高的上界。这样可以避免树退化为链状结构。
为什么两者结合效果极好？
- 路径压缩使得后续查询极快
- 按秩合并控制树的初始高度
- 二者结合，均摊复杂度为 $O(\alpha(n))$
✨ 代码实现
基础版本
union_find_basic.cpp
1#include <iostream>
2using namespace std;
3
4const int MAXN = 100005;
5int parent_arr[MAXN]; // 每个节点的父节点
6int rnk[MAXN]; // 秩（树高的上界）
7
8// 初始化：每个元素自成一个集合
9void init(int n) {
10 for (int i = 1; i <= n; i++) {
11 parent_arr[i] = i;
12 rnk[i] = 0;
13 }
14}
15
16// 查找根节点（带路径压缩）
17int find(int x) {
18 if (parent_arr[x] != x) {
19 parent_arr[x] = find(parent_arr[x]); // 路径压缩：直接连到根
20 }
21 return parent_arr[x];
22}
23
24// 合并两个集合（按秩合并）
25void unite(int x, int y) {
26 int rx = find(x), ry = find(y);
27 if (rx == ry) return; // 已在同一集合
28 if (rnk[rx] < rnk[ry]) swap(rx, ry);
29 parent_arr[ry] = rx; // 秩小的挂到秩大的下面
30 if (rnk[rx] == rnk[ry]) rnk[rx]++;
31}
32
33// 判断是否在同一集合
34bool connected(int x, int y) {
35 return find(x) == find(y);
36}
37
38int main() {
39 int n, m;
40 cin >> n >> m;
41 init(n);
42 while (m--) {
43 int op, x, y;
44 cin >> op >> x >> y;
45 if (op == 1) {
46 unite(x, y); // 合并x和y所在的集合
47 } else {
48 cout << (connected(x, y) ? "Yes" : "No") << endl;
49 }
50 }
51 return 0;
52}带集合大小的版本
union_find_size.cpp
1#include <iostream>
2using namespace std;
3
4const int MAXN = 100005;
5int parent_arr[MAXN];
6int sz[MAXN]; // 集合大小
7
8void init(int n) {
9 for (int i = 1; i <= n; i++) {
10 parent_arr[i] = i;
11 sz[i] = 1;
12 }
13}
14
15int find(int x) {
16 if (parent_arr[x] != x)
17 parent_arr[x] = find(parent_arr[x]);
18 return parent_arr[x];
19}
20
21// 按大小合并：小集合挂到大集合下
22void unite(int x, int y) {
23 int rx = find(x), ry = find(y);
24 if (rx == ry) return;
25 if (sz[rx] < sz[ry]) swap(rx, ry);
26 parent_arr[ry] = rx;
27 sz[rx] += sz[ry]; // 更新集合大小
28}
29
30// 查询x所在集合的大小
31int getSize(int x) {
32 return sz[find(x)];
33}Kruskal 最小生成树中的应用
kruskal.cpp
1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5const int MAXN = 100005;
6const int MAXM = 200005;
7
8struct Edge {
9 int u, v, w;
10 bool operator<(const Edge& o) const { return w < o.w; }
11} edges[MAXM];
12
13int parent_arr[MAXN], rnk[MAXN];
14
15void init(int n) {
16 for (int i = 1; i <= n; i++) { parent_arr[i] = i; rnk[i] = 0; }
17}
18
19int find(int x) {
20 if (parent_arr[x] != x) parent_arr[x] = find(parent_arr[x]);
21 return parent_arr[x];
22}
23
24bool unite(int x, int y) {
25 int rx = find(x), ry = find(y);
26 if (rx == ry) return false; // 已连通，加入会形成环
27 if (rnk[rx] < rnk[ry]) swap(rx, ry);
28 parent_arr[ry] = rx;
29 if (rnk[rx] == rnk[ry]) rnk[rx]++;
30 return true; // 成功合并
31}
32
33int main() {
34 int n, m;
35 cin >> n >> m;
36 for (int i = 0; i < m; i++)
37 cin >> edges[i].u >> edges[i].v >> edges[i].w;
38
39 sort(edges, edges + m); // 按边权排序
40 init(n);
41
42 int totalWeight = 0, edgeCount = 0;
43 for (int i = 0; i < m && edgeCount < n - 1; i++) {
44 if (unite(edges[i].u, edges[i].v)) {
45 totalWeight += edges[i].w;
46 edgeCount++;
47 }
48 }
49
50 if (edgeCount == n - 1)
51 cout << "最小生成树权值: " << totalWeight << endl;
52 else
53 cout << "图不连通" << endl;
54
55 return 0;
56}✨ 执行示例
以 5 个元素 {1, 2, 3, 4, 5} 为例，初始时每个元素各自成一个集合：
1初始状态: {1} {2} {3} {4} {5}
2parent: [1, 2, 3, 4, 5]
3
4操作 unite(1, 2):
5 find(1)=1, find(2)=2, 不同集合
6 合并: parent[2]=1
7 状态: {1,2} {3} {4} {5}
8 树: 1←2
9
10操作 unite(3, 4):
11 find(3)=3, find(4)=4
12 合并: parent[4]=3
13 状态: {1,2} {3,4} {5}
14 树: 1←2, 3←4
15
16操作 unite(2, 4):
17 find(2) → parent[2]=1 → 返回1
18 find(4) → parent[4]=3 → 返回3
19 合并: parent[3]=1
20 状态: {1,2,3,4} {5}
21 树: 1
22 / \
23 2 3
24 |
25 4
26
27操作 find(4):
28 4→3→1（找到根）
29 路径压缩: parent[4]=1, parent[3]=1
30 树变为: 1
31 /|\
32 2 3 4✨ 解题步骤详解
判断何时使用并查集
- 动态连通性问题：不断加边，查询两点是否连通
- 等价关系分组：将满足传递性关系的元素归为同类
- 最小生成树：Kruskal 算法的核心数据结构
- 判断图中是否有环：加边时若两端点已连通，则存在环
解题步骤
- 确定元素范围：明确有哪些元素需要管理
- 初始化：每个元素自成一个集合
- 处理合并操作：根据题意将元素合并
- 处理查询操作：判断两元素是否同组
经典应用场景
- 连通分量计数：最终有多少个不同的根 = 多少个连通分量
- 朋友圈问题：朋友的朋友是朋友，求有多少个朋友圈
- 岛屿合并：二维网格中相邻陆地属于同一岛屿
✨ 常见错误
- 忘记初始化：
parent[i]必须初始化为i，否则find会死循环或得到错误结果 - 合并时忘记先 find：直接
parent[x] = y是错误的，必须找到各自的根再合并 - 路径压缩写成循环版但忘记回溯：递归版路径压缩更简洁不易出错
- 用
rank作变量名：rank在部分编译器中是保留标识符，建议用rnk - 合并时没判断是否已在同一集合：虽然不会出错，但可能导致秩的错误更新
- 数组开小：注意元素编号范围，数组要开够
- 在需要撤销合并的场景仍用路径压缩：路径压缩是不可逆的，需要撤销时应使用按秩合并但不压缩路径
✨ 算法评价
时间复杂度
| 操作 | 朴素实现 | 路径压缩 | 路径压缩 + 按秩合并 |
|---|---|---|---|
| Find | $O(n)$ | 均摊 $O(\log n)$ | 均摊 $O(\alpha(n))$ |
| Union | $O(n)$ | 均摊 $O(\log n)$ | 均摊 $O(\alpha(n))$ |
其中 $\alpha(n)$ 是反阿克曼函数，对于任何实际输入规模（$n \leq 10^{80}$），$\alpha(n) \leq 4$。
空间复杂度
$O(n)$，需要存储每个元素的 parent 和 rank/size。
适用场景
- 需要动态维护集合的合并与查询
- 不需要拆分集合（标准并查集不支持分离操作）
- Kruskal 最小生成树、连通分量维护、等价类划分等
与其他数据结构的比较
- 相比 DFS/BFS 求连通分量：并查集支持在线动态加边，DFS/BFS 需要离线处理
- 相比平衡树：并查集不支持删除和拆分，但合并查询更快
- 相比哈希表：并查集天然支持传递性合并，哈希表需要额外逻辑
三、课后练习
编程练习
- 亲戚：L49930