并查集：从朴素实现到加权合并与路径压缩
发布 分类 coding
当前浏览器未执行 JavaScript，下面是本篇的 Markdown 原文，内容一字未改。
并查集解决的是「动态连通性」问题：不断加边，随时询问两个点是否连通。它的实现短到二十行，却是一门非常好用的手艺。
<!-- more -->
## 朴素版本与它的病
用 `fa[x]` 表示 x 的父节点，根节点满足 `fa[x] == x`：
```cpp
int fa[N];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
```
问题在于合并策略。如果每次都把左树挂到右树上，遇到退化的链就会把 `find` 拖成 $O(n)$。构造数据时是可以用 $1 \to 2 \to 3 \to \dots$ 这样的顺序把树拉成一条线的。
## 第一次进化：按大小合并
记录每棵树的大小，永远把小的挂到大的下面：
```cpp
int fa[N], sz[N];
void merge(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
fa[x] = y; sz[y] += sz[x];
}
```
这样树高被限制在 $O(\log n)$。直觉是：一个点每被抬升一次，它所在集合的大小至少翻倍，所以最多被抬 $\log n$ 次。
## 第二次进化：路径压缩
查询的时候顺手把路径上的所有点直接接到根上：
```cpp
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
```
这一行的代价是破坏了「树结构」的语义，好处是后续查询几乎变成一次数组访问。两种优化叠加后，均摊复杂度是 $O(\alpha(n))$，对于任何现实中的 n，$\alpha(n)$ 都不会超过 5。
| 优化 | 单次最坏 | 均摊 | 额外空间 |
| --- | --- | --- | --- |
| 无 | $O(n)$ | $O(n)$ | 1 个数组 |
| 按大小合并 | $O(\log n)$ | $O(\log n)$ | 多 1 个数组 |
| 路径压缩 | $O(\log n)$ | $O(\log n)$ | 无 |
| 两者结合 | $O(\log n)$ | $O(\alpha(n))$ | 多 1 个数组 |
## 什么时候用带权并查集
如果边还附带「差值」信息（例如「a 比 b 多 3」），就用带权并查集：把到根的权值 `d[x]` 一起维护，合并时注意权值的符号方向。经典题目是「食物链」与「银河英雄传说」。
```cpp
int find(int x) {
if (fa[x] == x) return x;
int r = find(fa[x]);
d[x] += d[fa[x]]; // 先递归到根，再累加
return fa[x] = r;
}
```
> [!WARN]
> 带权并查集里最常见的错误是合并时权值方向写反，尤其是把 `d[x] += d[fa[x]]` 和 `d[fa[x]] += d[x]` 弄混。写完先用小数据手算两条路径验证。
## 一个实用的封装
平时我会包一个 `DSU` 结构体，把 `init / find / merge / size` 收进去，顺便用 `const` 修饰查询，这样在算法题里能省掉一半的样板代码。
