并查集是处理不相交集合合并与查询问题的经典数据结构，核心操作包括查找元素所属集合、合并两个集合。基础并查集在多次查找操作后，树结构可能退化成链状，导致查询时间复杂度升高，路径压缩优化可以有效解决这个问题。
并查集基础原理
并查集通常用数组存储每个元素的父节点，初始时每个元素的父节点指向自身，代表每个元素独立成一个集合。主要有两个核心操作：
- 查找操作：找到元素所在集合的根节点，根节点的父节点是自身。
- 合并操作：将两个元素所在的集合合并，通常将一个集合的根节点指向另一个集合的根节点。
基础查找操作的实现逻辑如下：
// 基础查找函数，找到元素x的根节点
int find(int x, vector<int>& parent) {
// 如果父节点是自己，说明是根节点
if (parent[x] == x) {
return x;
}
// 否则递归查找父节点的根节点
return find(parent[x], parent);
}
路径压缩优化思路
基础查找操作中，如果集合的树结构深度较大，每次查找都需要递归遍历到根节点，效率较低。路径压缩的核心思想是：在查找某个元素的根节点时，把该元素到根节点路径上的所有节点的父节点都直接指向根节点，这样下次查找这些节点时可以直接定位到根节点，大幅降低树的高度。
路径压缩的实现方式是在查找操作中，递归找到根节点之后，再回溯将路径上的节点的父节点更新为根节点。这样可以将树的结构尽量压扁，减少后续查找的递归层数。
带路径压缩的并查集源码实现
完整的带路径压缩的并查集C++实现包含初始化、查找、合并三个核心方法，同时可以扩展集合大小查询等功能。以下是完整源码：
#include <vector>
#include <iostream>
using namespace std;
class UnionFind {
private:
// 存储每个元素的父节点
vector<int> parent;
// 存储每个集合的大小，用于合并优化（可选）
vector<int> size;
public:
// 初始化并查集，n为元素个数
UnionFind(int n) {
parent.resize(n);
size.resize(n, 1);
// 初始时每个元素的父节点指向自身
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 带路径压缩的查找操作
int find(int x) {
// 如果当前节点的父节点不是自身，递归查找父节点的根节点，同时路径压缩
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个元素所在的集合
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
// 如果根节点相同，说明已经在同一个集合，不需要合并
if (rootX == rootY) {
return;
}
// 按集合大小合并，小集合的根节点指向大集合的根节点，减少树高度
if (size[rootX] < size[rootY]) {
parent[rootX] = rootY;
size[rootY] += size[rootX];
} else {
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
}
// 判断两个元素是否在同一个集合
bool isConnected(int x, int y) {
return find(x) == find(y);
}
// 获取某个元素所在集合的大小
int getSize(int x) {
int root = find(x);
return size[root];
}
};
// 测试示例
int main() {
UnionFind uf(10);
// 合并0和1，2和3
uf.unite(0, 1);
uf.unite(2, 3);
cout << "0和1是否连通：" << uf.isConnected(0, 1) << endl;
cout << "0和2是否连通：" << uf.isConnected(0, 2) << endl;
// 合并1和2，此时0、1、2、3都在同一个集合
uf.unite(1, 2);
cout << "0和3是否连通：" << uf.isConnected(0, 3) << endl;
cout << "0所在集合的大小：" << uf.getSize(0) << endl;
return 0;
}
算法复杂度分析
未优化的并查集查找操作时间复杂度最坏为O(n)，而带路径压缩的并查集，结合按大小合并的优化，单次操作的平均时间复杂度接近O(1)，整体效率非常高，适合处理大规模的集合合并查询场景。
应用场景说明
带路径压缩的并查集常用于以下场景：
- 判断图的连通分量数量
- Kruskal最小生成树算法中判断边是否形成环
- 社交网络中判断两个人是否属于同一个社交圈
- 动态连通性问题处理