快速回答"这两个元素属于同一组吗"以及"把这两组合并成一组"——并查集用接近 O(1) 的时间支持这两种操作。
假设班里 8 个同学要分成若干小组，我们需要快速回答两类问题：
① 查："1 号和 5 号是一组吗？"——Find(1) == Find(5) ?
② 并："把 3 号所在的组和 7 号所在的组合并成一组。"——Union(3, 7)
并查集的做法是：每个组推选一个代表（根节点），每个人记住自己的上级是谁。要判断两人是否同组，只需看他们各自追溯到的代表是否相同。
并查集只需要一个数组 parent[]，parent[i] 存储 i 的上级是谁。根节点的上级是自己：parent[root] == root。
初始时每个人都是独立的一组，上级指向自己：
从 x 出发，沿着 parent 指针一路往上，直到找到根（parent[x] == x 的节点），这就是 x 所在组的代表。
| 1 | int Find(int x) { |
| 2 | while (parent[x] != x) // 还没到根，继续往上 |
| 3 | x = parent[x]; |
| 4 | return x; |
| 5 | } |
问题是：如果树退化成一条链（每次都把新元素挂在最深处），Find 需要 O(n) 时间。下面的路径压缩解决这个问题。
查找根的过程中，顺手把沿途所有节点的 parent 直接指向根。下次再查这条路上的任何节点，一步就到根了。
Find 的均摊时间复杂度接近 O(1)（严格来说是 O(α(n))，α 是反阿克曼函数，实际上不超过 5）。
| 1 | int Find(int x) { |
| 2 | if (parent[x] != x) |
| 3 | parent[x] = Find(parent[x]); // 递归找根，顺手把 parent[x] 直接指向根 |
| 4 | return parent[x]; |
| 5 | } |
| 6 | |
| 7 | // 更简洁的一行版本（等价） |
| 8 | int Find(int x) { return parent[x] == x ? x : parent[x] = Find(parent[x]); } |
合并两个集合，只需找到各自的根，然后让其中一个根的 parent 指向另一个根——两棵树就合并成了一棵。
| 1 | void Union(int x, int y) { |
| 2 | int rx = Find(x), ry = Find(y); // 找到各自的根 |
| 3 | if (rx != ry) // 不同组才需要合并 |
| 4 | parent[rx] = ry; // 把 rx 的根挂到 ry 下面 |
| 5 | } |
| 6 | |
| 7 | // 判断是否同组 |
| 8 | bool Same(int x, int y) { return Find(x) == Find(y); } |
size[] 记录每棵树的节点数，合并时把小的挂到大的上。实际竞赛中，只加路径压缩通常就够用了——两者同时使用可以达到理论最优。
| 1 | const int MAXN = 100005; |
| 2 | int parent[MAXN], sz[MAXN]; |
| 3 | |
| 4 | void init(int n) { |
| 5 | for (int i = 1; i <= n; i++) |
| 6 | parent[i] = i, sz[i] = 1; // 每人自成一组，大小为 1 |
| 7 | } |
| 8 | |
| 9 | int Find(int x) { |
| 10 | return parent[x] == x ? x : parent[x] = Find(parent[x]); |
| 11 | } |
| 12 | |
| 13 | void Union(int x, int y) { |
| 14 | int rx = Find(x), ry = Find(y); |
| 15 | if (rx == ry) return; // 已经同组，不用合并 |
| 16 | if (sz[rx] < sz[ry]) swap(rx, ry); // 小树挂到大树 |
| 17 | parent[ry] = rx; |
| 18 | sz[rx] += sz[ry]; |
| 19 | } |
| 20 | |
| 21 | bool Same(int x, int y) { return Find(x) == Find(y); } |
| 题型 | 并查集的用法 | 关键操作 |
|---|---|---|
| 判断连通性 | 把图的每条边两端 Union，最后查询两点是否 Same | Union + Same |
| 统计连通分量数 | 初始分量数 = n，每次成功 Union 就 −1 | Union + 计数 |
| Kruskal 最小生成树 | 按边权从小到大枚举，若两端不同组则加入 MST 并 Union | Sort + Union + Same |
| 朋友圈 / 社交分组 | "A 认识 B，B 认识 C"则三人同组，查询任意两人是否认识 | Union + Same |
| 判断图是否有环 | 加边前若两端已 Same，则加这条边会形成环 | Same（加边前检查） |
parent[] 数组，支持合并集合和查询是否同集合两种操作。Find 沿 parent 链找根；加上路径压缩后均摊接近 O(1)。Union 把两个根连起来；加上按大小合并防止树过高。