Appearance
并查集
概念
并查集（Union-Find Set，又称不相交集合 Disjoint Set Union）用一个数组维护若干个互不相交的动态集合，只支持三个操作：
| 操作 | 记号 | 含义 |
|---|---|---|
| 初始化 | Initial(S) | 每个元素各自成一个单元素集合 |
| 查 | Find(S, x) | 找 x 所在集合的代表（根），也用来判断两个元素是否同属一个集合 |
| 并 | Union(S, Root1, Root2) | 把两个不相交集合并成一个 |
它本质上是一片森林，用树的双亲表示法存：数组 parent[i] 记录元素 i 的双亲下标，根结点的 parent 记为 −1。
一句话理解：并查集是"认老大"的结构——每个集合选一个根当老大，查就是顺藤摸瓜找老大，并就是让一个老大给另一个老大当小弟。
原理
存储与基本操作
下标: 0 1 2 3 4
parent: -1 0 0 -1 3
集合: {0,1,2} {3,4}Find(x)：从 x 出发一路parent往上走，直到parent == -1，那个下标就是代表。Union(a, b)：分别 Find 出两个根，若根相同则已在同一集合、什么都不做；否则把其中一个根的 parent 指向另一个根。
朴素写法的问题：Union 时若总是把大树挂到小树下，树会退化成一条链，n 次操作后 Find 变成 O(n)。
优化一：按规模（或按秩）合并
合并时永远让小树挂到大树下面（结点数少的做子树）。需要一个 size[] 数组记录每棵树的结点数。
效果：每次一个结点所在子树规模至少翻倍，所以树高不超过
优化二：路径压缩
Find 找到根之后，顺手把查找路径上所有结点直接挂到根下。
压缩前: 5 → 4 → 3 → 2 → 1(根)
压缩后: 5 ↘
4 → 1(根)
3 ↗
2 ↗效果：这次多花一点指针操作，之后这些结点的 Find 都是 O(1)。
两种优化合用的复杂度
| 方案 | 单次操作复杂度 |
|---|---|
| 朴素（不优化） | 最坏 O(n) |
| 只用按规模合并（或只路径压缩） | 均摊 O(log n) |
| 按规模合并 + 路径压缩 | 均摊 O(α(n)) |
其中 α 是反阿克曼函数（Inverse Ackermann），增长极慢：在 n 不超过
记忆：并查集几乎是"免费"的数据结构——代码十几行，复杂度可视作 O(1)。408 里它通常作为工具出现在 Kruskal 算法、连通性判断中，很少单独出大题，但"判断无向图是否有环""求连通分量个数"是选择题常客。
典型应用
| 应用 | 做法 |
|---|---|
| 求无向图连通分量个数 | 每条边两端 Union，最后数 parent[i] == -1 的个数 |
| 判无向图是否有环 | 加一条边 (u,v) 前先 Find：若已同根，则这条边必然成环 |
| Kruskal 最小生成树 | 边按权排序，逐条取；两端不同集合才收下并 Union |
| 等价类 / 亲戚关系 / 朋友圈 | 关系即 Union，查询即 Find |
示例
例：10 个元素，依次合并，求连通块
元素 0~9 初始各自成集合，依次执行合并： (0,1) (1,2) (3,4) (5,6) (7,8) (8,9) (2,6) 采用"按规模合并 + 路径压缩"，写出每步后的 parent 数组，并回答：最终有几个集合？2 和 6 是否在同一集合？
完整推导过程：
初始：parent = [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]，size 全为 1。
| 步 | 操作 | 两个根 | 谁挂谁 | parent 之后 | 集合 |
|---|---|---|---|---|---|
| 1 | (0,1) | 0, 1 | 1 → 0 | [-1,0,-1,-1,-1,-1,-1,-1,-1,-1] | {0,1} 等 9 个 |
| 2 | (1,2) | 0, 2 | 2 → 0 | [-1,0,0,-1,-1,-1,-1,-1,-1,-1] | {0,1,2} 等 8 个 |
| 3 | (3,4) | 3, 4 | 4 → 3 | [-1,0,0,-1,3,-1,-1,-1,-1,-1] | 7 个 |
| 4 | (5,6) | 5, 6 | 6 → 5 | [-1,0,0,-1,3,-1,5,-1,-1,-1] | 6 个 |
| 5 | (7,8) | 7, 8 | 8 → 7 | [-1,0,0,-1,3,-1,5,-1,7,-1] | 5 个 |
| 6 | (8,9) | 7, 9 | 9 → 7 | [-1,0,0,-1,3,-1,5,-1,7,7] | 4 个 |
| 7 | (2,6) | 0, 5 | 5 → 0（size 3 > 2，小树 5 挂大树 0） | [-1,0,0,-1,3,0,5,-1,7,7] | 3 个 |
第七步的关键：Find(2) 得到 0，Find(6) 先沿 6→5 得根 5。两棵树规模分别为 3 和 2，所以规模小的 5 挂到 0 下，而不是反过来。
最终 parent = [-1, 0, 0, -1, 3, 0, 5, -1, 7, 7]，根有三个：0、3、7。
- 3 个集合：{0,1,2,5,6}、{3,4}、{7,8,9}。
- 2 和 6 在同一集合：Find(2) = 0，Find(6) 沿 6→5→0 也得到 0。注意这最后一次 Find 会顺带路径压缩，把 6 直接挂到 0 下，parent 数组变为
[-1,0,0,-1,3,0,0,-1,7,7]。
对应的森林：
0 3 7
/ | \ | / \
1 2 5 4 8 9
|
6C 语言：按规模合并 + 路径压缩
#include <stdio.h>
#define N 10
int parent[N], sz[N]; /* 根的 parent 为 -1；sz 仅在根上有意义 */
void initial(int n) {
for (int i = 0; i < n; i++) { parent[i] = -1; sz[i] = 1; }
}
/* 带路径压缩的 Find，返回根下标 */
int find(int x) {
int r = x;
while (parent[r] != -1) r = parent[r]; /* 第一遍：找根 */
while (x != r) { /* 第二遍：把路径上所有点直挂到根 */
int p = parent[x];
parent[x] = r;
x = p;
}
return r;
}
/* 按规模合并，返回 1 表示真的合并了，0 表示本来就同集合 */
int unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return 0;
if (sz[ra] < sz[rb]) { int t = ra; ra = rb; rb = t; } /* 小树挂大树 */
parent[rb] = ra;
sz[ra] += sz[rb];
return 1;
}
int countSets(int n) {
int c = 0;
for (int i = 0; i < n; i++) if (parent[i] == -1) c++;
return c;
}
int main(void) {
initial(N);
int ops[][2] = {{0,1},{1,2},{3,4},{5,6},{7,8},{8,9},{2,6}};
for (int i = 0; i < 7; i++) {
int a = ops[i][0], b = ops[i][1];
printf("union(%d,%d): %s 集合数 = %d\n",
a, b, unite(a, b) ? "合并" : "已连通", countSets(N));
}
printf("2 与 6 同集合? %s\n", find(2) == find(6) ? "是" : "否"); /* 是 */
printf("最终 parent: ");
for (int i = 0; i < N; i++) printf("%d ", parent[i]);
printf("\n最终集合数 = %d\n", countSets(N)); /* 3 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
class UF:
def __init__(self, n):
self.parent = [-1] * n # 根的 parent 为 -1
self.size = [1] * n
def find(self, x):
r = x
while self.parent[r] != -1:
r = self.parent[r]
while x != r: # 路径压缩
self.parent[x], x = r, self.parent[x]
return r
def unite(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def count(self):
return sum(1 for p in self.parent if p == -1)
uf = UF(10)
for a, b in [(0,1),(1,2),(3,4),(5,6),(7,8),(8,9),(2,6)]:
print(f"union({a},{b}): {'合并' if uf.unite(a,b) else '已连通'} 集合数 = {uf.count()}")
print("2 与 6 同集合?", uf.find(2) == uf.find(6)) # True
print("parent:", uf.parent, " 集合数:", uf.count()) # 3
# 应用：无向图判环 —— 加边前若两端已连通，则必成环
def has_cycle(n, edges):
uf = UF(n)
for u, v in edges:
if not uf.unite(u, v):
return True, (u, v)
return False, None
print(has_cycle(4, [(0,1),(1,2),(2,3)])) # (False, None) 树，无环
print(has_cycle(4, [(0,1),(1,2),(2,3),(3,0)])) # (True, (3, 0)) 成环
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- 存储方式：树的双亲表示法，数组
parent[]，根结点 parent = −1（也有的教材用parent[i] = i，根标记不同但本质一致）。 - 两种优化：按规模（秩）合并 控制树高 ≤ log₂n + 1；路径压缩 在 Find 时把路径拉平。
- 两者合用，均摊复杂度 O(α(n))，α(n) ≤ 4，实用上视作常数。
- Find 用来判同属，Union 用来合并；
Find(a) == Find(b)即"a、b 连通"。
2. 解题套路
- 求连通分量数 = 执行完所有 Union 后，统计
parent[i] == -1的个数（只有根才是 −1，别数成"parent 等于自己"）。 - 判环：逐条加边，若某条边两端 Find 结果相同 → 有环。
- 手算 Union 序列时，务必先看清题目是否要求"按规模合并"——若要求，则每步都要比较两棵树的大小，方向反了后续树形全错。
3. 易错点
Union的参数是两个根（代表元素），不是任意两个元素。传普通元素进去会挂错地方——正确做法是函数内部先各自 Find。- 路径压缩不改变 Find 的返回值，只改变树的形状；它也不改变"哪些元素在同一集合"这一事实。
- 按规模合并后，只有根的
size有意义，非根结点的size是过期数据，不要再读它。 - 并查集不支持"拆分"操作（把一个集合拆回两个），也不能高效枚举某个集合的所有成员。需要后者请另用链表/哈希。
- 它和"树"章节的双亲表示法是一回事，只是这里的树不保证是二叉树，一个根可以有任意多个孩子。
小结
- 并查集用
parent[]数组表示森林，只提供 Find 与 Union 两个操作，解决"连通性"这类等价关系问题。 - 按规模合并 + 路径压缩后，均摊 O(α(n))，实际可当 O(1)；代码极短，是图算法的常备零件。
- 判同集合 = 比较 Find 结果；求连通块数 = 数
parent == -1的根。 - 下一步：换一种"用数组表示树"的思路，看堆如何用连续空间实现优先队列。
下一篇：堆与优先队列
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。