什么是并查集
并查集，英文叫 Union-Find，也叫不相交集合。它专门处理"把一些元素合并成集合"和"查询两个元素是否在同一个集合"这两个操作，而且都很快。
想象一下，你有一堆人，需要不断告诉你：谁和谁是亲戚，谁和谁不是亲戚。每告诉一对关系，你可能要把两个家族合并起来。然后你还要经常问：某两个人是不是亲戚？
用数组和链表做这件事，每次合并要遍历一个集合的所有元素，效率很低。并查集就是来解决这个问题的。
并查集的核心思想
并查集用一种很巧妙的方式表示集合：每个元素指向一个"代表"，所有属于同一个集合的元素，最终都指向同一个代表。
打个比方：若干家庭各自选出一个族长，所有家庭成员都认族长为头。并查集就是维护这个"谁认谁当头"的关系。
具体实现上，每个元素有一个父节点。如果一个元素的父节点是它自己，那它就是代表。查找两个元素是否在同一个集合，就是看它们的代表是不是同一个人。
基本操作与代码实现
初始化
一开始，每个元素都是独立的，自己是自己的代表：
vector parent(n + 1);
vector rank(n + 1); // 秩，用于按秩合并优化
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i; // 每个元素的父节点是自己
rank[i] = 0; // 初始秩为0
}
}
查找 find
查找操作就是找出一个元素所在集合的代表。朴素写法：
int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]);
}
但这样树可能很深，查找效率会退化。于是引入路径压缩：
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩：直接指向根节点
}
return parent[x];
}
路径压缩的意思是：沿途所有节点都直接认根节点当代表，就像大家都记住了族长是谁，不用每次都顺着链条往上找了。
合并 union
合并两个集合，就是把一个集合的代表接到另一个代表的下面：
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]++;
}
}
按秩合并的意思是：矮树接到高树下面，这样树不容易变深。两个秩相同的树合并，秩才加一。
判断连通
判断两个元素是否在同一个集合：
bool connected(int x, int y) {
return find(x) == find(y);
}
典型题：亲戚问题
并查集的经典入门题：给出若干对"是亲戚"的关系，问某两个人是否是亲戚。
int n, m, p; // n个人，m对亲戚关系，p个询问
cin >> n >> m >> p;
init(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
union(x, y);
}
for (int i = 0; i < p; i++) {
int x, y;
cin >> x >> y;
if (connected(x, y)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
思路很简单：每对亲戚关系就是一次合并操作，然后每个询问只需要一次查找比较。
典型题：连通分量个数
给一个无向图，问它有几个连通分量。用并查集非常方便：
int countComponents(int n, vector>& edges) {
init(n);
for (auto& e : edges) {
union(e[0], e[1]);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i) cnt++;
}
return cnt;
}
思路：合并所有边，最后数一数有多少个代表，就有多少个连通分量。
并查集还能做什么
- 合并集合：动态合并多个集合，查询元素归属；
- 连通分量：无向图连通块个数、岛屿数量；
- 最小生成树：Kruskal 算法用并查集判断是否成环；
- 亲戚关系：传递闭包问题；
- 等式约束：判断一组等式是否矛盾；
- 分组问题：把有关系的元素归到同一组。
并查集的易错点
- 忘了路径压缩：不压缩会退化成链表，查询变成 O(n)；
- 忘了按秩合并：不按秩合并，树可能变得又深又歪；
- 下标从0还是从1开始：看清楚题目输入；
- 合并时没判断是否 already connected：不加判断会导致重复操作和错误；
- 用 long long 的情况：如果元素编号很大，用 long long 存 parent。
什么时候用并查集
看到这些问题描述，就可以考虑并查集：
- 若干元素不断合并，问两个元素是否在同一个集合；
- 无向图的连通分量个数；
- 需要判断是否会成环；
- 传递性的关系：a 和 b 是亲戚，b 和 c 是亲戚，问 a 和 c 是不是亲戚。
这一篇先记住什么
- 并查集处理集合合并与查询，平均近乎 O(1)；
- find 用路径压缩，union 用按秩合并，这是标准优化；
- connected 判断两个元素是否在同一个集合；
- 典型应用：亲戚关系、连通分量、Kruskal；
- 看到"连通""合并""分组""传递闭包"就想到并查集。
下一篇继续数据结构：堆与优先队列。它是处理最值问题的利器，能高效维护动态集合的最大值或最小值。