并查集（Disjoint Set Union，简称 DSU，也叫 Union-Find）是一种处理不相交集合的合并与查询问题的数据结构。它回答两个核心问题：某个元素属于哪个集合，以及如何把两个集合合并成一个。判断图中的连通分量、检测无向图是否有环、解决动态连通性问题，背后都离不开并查集。它的实现非常简洁，但效率极高，配合路径压缩和按秩合并后，单次操作的时间复杂度可以逼近常数级别。
并查集的基本原理与实现
并查集的核心思想是用数组模拟森林。每个节点记录自己的父节点，parent[i]表示第 i 个元素的父节点编号。如果一个节点的父节点是它自己，说明它是这个集合的根节点，也就是整个集合的代表。判断两个元素是否属于同一集合，只需分别找到它们的根节点，若根相同，则同属一个集合。
初始状态下，每个元素自成一个集合，所有节点的父节点都指向自己。查找操作沿着父指针一路向上，直到遇到根节点；合并操作则把其中一个集合的根挂到另一个集合的根下面。下面是最朴素的实现：
class UnionFind {
public:
vector<int> parent;
// 初始化：每个元素的父节点都是自己
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}
// 查找根节点
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
// 合并两个集合
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx != ry) parent[rx] = ry;
}
// 判断是否同属一个集合
bool connected(int x, int y) {
return find(x) == find(y);
}
};这个实现已经能正确工作了，但存在一个隐患：树的形态完全取决于合并的顺序。如果每次都把大树挂到小树下面，或者按链式结构依次合并，整棵树可能退化成一条长链。此时查找操作要从叶子走到根，最坏时间复杂度达到 O(n)，在频繁查询的场景下性能难以接受。
路径压缩：让树越走越扁平
路径压缩的思路很简单：在执行查找操作时，顺便把查找路径上经过的所有节点直接挂到根节点下面。这样一来，第一次查找可能要走很长的路径，但之后这条路径上的所有节点再到根节点都只需一步，树会被迅速压扁。
实现上有两种常见写法。第一种是两步一跳的迭代写法，让每个节点直接指向它的祖父节点，代码短且不消耗递归栈：
int find(int x) {
while (parent[x] != x) {
// 隔代压缩：让x直接指向祖父节点
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}第二种是完全压缩的递归写法，查找返回时把路径上每个节点的父节点统一改成根，压缩得更彻底：
int find(int x) {
if (parent[x] != x) {
// 递归找到根后，把x直接挂到根下
parent[x] = find(parent[x]);
}
return parent[x];
}两种写法的均摊效果都很好。需要注意递归版本在极端深度的树下可能导致栈溢出，竞赛或工程中更推荐迭代版本。路径压缩只优化查找，不影响合并逻辑的正确性，因为它只是在改变树的结构，并没有改变集合的从属关系。
配合按秩合并，复杂度逼近常数
单用路径压缩，单次操作的均摊复杂度是 O(log n)；单用按秩合并（或按大小合并），同样是 O(log n)。但两者结合后，单次操作的均摊复杂度会降到反阿克曼函数 α(n) 的级别。α(n) 增长极其缓慢，对于宇宙中任何实际规模的数据，它都不会超过 4，因此工程上可以近似看作常数时间。
按秩合并的思路是用一个 rank 数组记录每棵树的高度（或近似高度），合并时永远把矮树挂到高树下面，避免树的高度增长：
class UnionFind {
vector<int> parent, rnk;
public:
UnionFind(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rnk[rx] < rnk[ry]) swap(rx, ry);
parent[ry] = rx; // 矮树挂到高树下
if (rnk[rx] == rnk[ry]) rnk[rx]++;
}
};使用按大小合并也是常见替代方案：记录每个集合的元素个数，合并时把小集合挂到大集合下面。两者效果相当，按大小合并的实现更直观，工程中用得也很多。
典型应用场景与常见误区
并查集最常见的应用是连通性判断。例如给定一张无向图，询问任意两点之间是否连通：把每条边依次合并，查询时比较两点的根节点即可。另一个经典应用是判环：遍历图的边时，如果某条边的两个端点已经属于同一集合，说明加上这条边必然成环。克鲁斯卡尔（Kruskal）最小生成树算法正是借助并查集来跳过会形成环的边。
写并查集时有几个容易踩的坑。一是忘记判断合并的两个元素是否已经同属一个集合，导致按大小合并时的计数出错；二是路径压缩写在了合并之外，没有真正落到 find 里；三是处理带权或需要还原集合内部信息的场景时，直接套模板，忽略了需要额外维护每个节点到根的距离或权值，这类扩展通常叫带权并查集，需要在路径压缩的同时同步更新节点权值。
总结一下，并查集的精髓在于用极简的结构解决动态集合关系问题。掌握路径压缩的两种写法，再配合按秩合并，几乎可以应对所有需要维护不相交集合的场景。刷题时遇到连通性、分组、判环等关键词，第一时间想到并查集，往往能打开解题思路。