并查集是最简洁而强大的数据结构之一，本文全面梳理其应用。
一、基础并查集
维护集合的合并与查找：
int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }路径压缩后，find 的复杂度接近 O(1)。
二、按秩合并优化
int 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[y] = x, sz[x] += sz[y];
}结合路径压缩和按秩合并，复杂度为 O(α(n))（反阿克曼函数，实际近乎常数）。
三、带权并查集
维护节点到根节点的距离/关系：
- 食物链问题（POJ 1182 / 洛谷 P2024）
- 判断两点间关系（如奇偶性、相对位置）
核心：在 find 时更新权值，在 merge 时设置权值关系。
四、种类并查集（扩展域）
将每个节点拆成多个"种类"，处理对立关系：
- 敌人的敌人是朋友
- 二分图染色判定
常用技巧：设 x 和 x+n 分别代表 x 属于不同种类。
五、可撤销并查集
支持回溯到历史状态：
- 不能使用路径压缩（会破坏结构）
- 只能用按秩合并
- 用栈记录每次合并操作
- 配合线段树分治解决动态图问题
推荐练习：
- 基础：洛谷 P3367
- 带权：洛谷 P1196 银河英雄传说
- 种类：洛谷 P2024 食物链
- 可撤销：洛谷 P3402
暂无评论，快来抢沙发吧~ 🛋️