Appearance
并查集（Union-Find）
为什么需要并查集
给你一堆元素，不断地做两件事：把两个集合合并、查某两个元素是不是同一个集合里的。听起来简单，但如果每次都遍历整个集合去找，效率极其拉胯。并查集就是专门解决这类"动态连通性"问题的数据结构——Kruskal 算法判断加边会不会成环，靠的就是它。
408 考研中并查集是树与森林章节的延伸考点，常与 Kruskal 算法结合出题，选择题考操作过程和复杂度，应用题考手算森林状态。
核心思想
并查集用森林表示若干不相交集合，每棵树代表一个集合，树的根节点就是这个集合的代表元素。
- 双亲表示法存储：用一个
parent[]数组，parent[i]记录元素 i 的父节点；根节点的parent值为 -1（或指向自身） - Find 操作：从给定元素沿
parent链一路向上，直到找到根节点，返回根节点编号——两个元素的根相同，说明在同一集合 - Union 操作：分别找到两个元素所在集合的根，然后让其中一个根指向另一个根，两棵树合并为一棵
- 优化手段：路径压缩（Find 时将路径上的节点直接挂到根）和按秩合并（Union 时矮树挂到高树下），可以把操作复杂度压到接近 O(1)
操作详解
存储结构——双亲表示法
c
#define MAX 100
int parent[MAX]; // parent[i] 存储元素 i 的父节点，根节点为 -1
// 初始化：每个元素独立成集合
void Init(int n) {
for (int i = 0; i < n; i++)
parent[i] = -1; // -1 表示根节点
}初始状态下，每个元素的 parent 都是 -1，意味着每个元素自己就是一棵树的根，整个森林有 n 棵单节点的树。
Find 操作
朴素版：从元素 x 出发，沿 parent 链一直向上走，直到遇到 parent[x] == -1 的根节点。
c
// 朴素 Find：返回 x 所在集合的根
int Find(int x) {
while (parent[x] != -1)
x = parent[x];
return x;
}最坏情况下树退化为链表，每次 Find 的时间复杂度为 O(n)。
路径压缩版：在 Find 的过程中，把路径上经过的所有节点直接挂到根节点下，下次再查这些节点就是 O(1)。
c
// 路径压缩 Find（递归版）
int Find(int x) {
if (parent[x] == -1)
return x;
parent[x] = Find(parent[x]); // 递归找根，顺便把 x 直接挂到根
return parent[x];
}
// 路径压缩 Find（迭代版）
int Find(int x) {
int root = x;
while (parent[root] != -1) // 先找到根
root = parent[root];
while (x != root) { // 再把路径上的节点全部直接挂到根
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}⚠️ 易错：路径压缩只改变 Find 路径上节点的
parent指向，让它们直接指向根。集合的逻辑划分没有任何变化——同一集合里的元素还是那些元素，只是树的形态变扁了。
Union 操作
朴素版：找到两个元素的根，直接让一个根指向另一个根。
c
// 朴素 Union：合并 x 和 y 所在的集合
void Union(int x, int y) {
int rx = Find(x);
int ry = Find(y);
if (rx != ry)
parent[rx] = ry; // 让 rx 的根指向 ry
}按秩合并版：维护一个 rank[] 数组记录每棵树的高度上界，合并时让矮树挂到高树下面，避免树越长越高。
c
int rank[MAX]; // rank[i] 表示以 i 为根的树的高度上界
void Init(int n) {
for (int i = 0; i < n; i++) {
parent[i] = -1;
rank[i] = 0; // 初始每棵树高度为 0
}
}
// 按秩合并
void Union(int x, int y) {
int rx = Find(x);
int ry = Find(y);
if (rx == ry) return; // 已在同一集合
if (rank[rx] < rank[ry]) {
parent[rx] = ry; // 矮树挂到高树下
} else if (rank[rx] > rank[ry]) {
parent[ry] = rx;
} else {
parent[ry] = rx; // 等高时任选一个作根
rank[rx]++; // 新树高度 +1
}
}⚠️ 易错：按秩合并的
rank在路径压缩后不再精确表示树高，只是一个上界。路径压缩会降低实际树高，但不会去更新rank值——因为精确维护 rank 代价太大，而且上界已经足够保证复杂度。考研选择题偶尔会考这个细节。
完整手算示例
初始集合 {0, 1, 2, 3, 4}，执行操作序列：Union(0,1), Union(2,3), Union(1,3), Union(0,4)。使用朴素 Union（让前者的根指向后者的根）。
初始状态: 每个元素独立（parent 均为 -1）
0 1 2 3 4
第1步: Union(0, 1) — Find(0)=0, Find(1)=1, parent[0]=1
1 2 3 4
|
0
第2步: Union(2, 3) — Find(2)=2, Find(3)=3, parent[2]=3
1 3 4
| |
0 2
第3步: Union(1, 3) — Find(1)=1, Find(3)=3, parent[1]=3
3 4
/ \
1 2
|
0
第4步: Union(0, 4) — Find(0): 0→1→3, 根为3; Find(4)=4, parent[3]=4
4
|
3
/ \
1 2
|
0parent 数组变化过程：
| 操作 | parent[0] | parent[1] | parent[2] | parent[3] | parent[4] |
|---|---|---|---|---|---|
| 初始 | -1 | -1 | -1 | -1 | -1 |
| Union(0,1) | 1 | -1 | -1 | -1 | -1 |
| Union(2,3) | 1 | -1 | 3 | -1 | -1 |
| Union(1,3) | 1 | 3 | 3 | -1 | -1 |
| Union(0,4) | 1 | 3 | 3 | 4 | -1 |
应用：Kruskal 算法
Kruskal 算法在构建最小生成树时，需要判断一条边的两个端点是否已在同一连通分量中（加入则会成环）。并查集完美适配这个需求：
- 初始化并查集，每个顶点独立成集合
- 将所有边按权值排序
- 依次取权值最小的边 (u, v)，执行
Find(u)和Find(v) - 若根不同，说明 u、v 不连通，选中该边并
Union(u, v) - 若根相同，跳过该边（加入会形成回路）
等价类划分
并查集也可用于等价类划分问题：给出若干"等价关系"对 (a, b)，将所有等价的元素归入同一类。每读入一对 (a, b)，执行 Union(a, b) 即可，最终 Find 值相同的元素属于同一等价类。
复杂度分析
| 实现方式 | Find | Union | 说明 |
|---|---|---|---|
| 朴素实现 | O(n) | O(n) | Union 包含两次 Find，树可能退化为链 |
| 路径压缩 | O(log n) | O(log n) | Find 时压缩路径，均摊复杂度 |
| 按秩合并 | O(log n) | O(log n) | 限制树高，最坏 O(log n) |
| 路径压缩 + 按秩合并 | O(α(n)) | O(α(n)) | α 为反阿克曼函数，实际可视为 O(1) |
空间复杂度：O(n)，需要 parent[] 数组（按秩合并额外需要 rank[] 数组）。
α(n) 是反阿克曼函数，增长极其缓慢。对于任何实际可能出现的 n 值（哪怕是宇宙中的原子数），α(n) 都不超过 5。408 考试中一般只要求知道"接近常数"即可。
考研高频考点
- ⭐ 给定操作序列，画出并查集的森林状态（应用题高频，手算 parent 数组变化）
- ⭐ 路径压缩的过程与效果（选择题考"压缩后的树形态"）
- ⭐ 按秩合并的规则（矮树挂高树，等高则任选并 rank+1）
- ⭐ Find 和 Union 操作的时间复杂度（朴素 vs 优化后的对比）
- ⭐ 并查集在 Kruskal 算法中的应用（判断是否成环）
- ⭐ 并查集的存储结构——双亲表示法（parent 数组的含义与初始化）
- 等价类划分问题的求解（Union-Find 的直接应用场景）
- 路径压缩与按秩合并同时使用时的复杂度为 O(α(n))（选择题常考的结论）
相关知识
- 哈夫曼树：同样是自底向上合并的树型结构，贪心策略有异曲同工之处
- 树与森林的转换：并查集本质上是用森林表示集合，涉及树的双亲表示法
- Kruskal 算法：Kruskal 算法的核心依赖并查集判断连通性