并查集通过路径压缩和按秩合并高效处理集合合并与查询，支持连通性判断、求连通分量等操作，常用于Kruskal算法、岛屿问题等场景。
并查集（Union-Find）是一种高效处理不相交集合合并与查询的数据结构，常用于解决连通性问题，比如判断图中两个节点是否连通、求连通分量个数等。在 C++ 中实现并查集非常直观，核心操作包括查找（find）和合并（union）。通过路径压缩和按秩合并优化，可以将时间复杂度接近常数级别。
基本结构与初始化
并查集通常用一个数组 parent 来表示每个元素的父节点，初始时每个元素的父节点是自己，表示各自独立成一个集合。
还可以引入 rank 数组来记录每棵树的“秩”（近似高度），用于优化合并操作。
class UnionFind {
public:
vector parent;
vector rank;
// 构造函数，初始化 n 个独立元素
UnionFind(int n) {
parent.resize(n);
rank.resize(n, 0);
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 (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
// 判断两个元素是否属于同一集合
bool connected(int x, int y) {
return find(x) == find(y);
}
};
关键优化：路径压缩与按秩合并
这两个优化策略显著提升并查集效率：
立即学习“C++免费学习笔记（深入）”；
- 路径压缩：在 find 过程中，把沿途所有节点直接连到根节点，降低后续查找成本。
- 按秩合并：合并时尽量让较矮的树接在较高的树下，避免生成过深的树，控制整体高度。
经过这两种优化后，单次操作的平均时间复杂度接近 O(α(n))，其中 α 是阿克曼函数的反函数，增长极慢，可视为常数。
实际应用场景举例
假设要判断无向图中边的连接是否会形成环，可以用并查集逐条处理边：
#include#include using namespace std; int main() { int n = 5; UnionFind uf(n); // 添加边 (0,1), (1,2), (3,4) uf.unite(0, 1); uf.unite(1, 2); uf.unite(3, 4); cout << "0 和 2 连通吗？" << (uf.connected(0, 2) ? "是" : "否") << endl; // 是 cout << "0 和 3 连通吗？" << (uf.connected(0, 3) ? "是" : "否") << endl; // 否 uf.unite(2, 3); cout << "0 和 4 连通了吗？" << (uf.connected(0, 4) ? "是" : "否") << endl; // 是 return 0; }
总结与扩展建议
并查集适合动态维护集合的合并与查询，代码简洁且效率高。在算法竞赛或工程中常用于：
- Kruskal 最小生成树算法
- 岛屿数量问题（替代 DFS/BFS）
- 社交网络中的好友关系连通判断
可以根据需要扩展支持集合大小统计、删除操作（需更复杂结构）等功能。掌握基础实现后，灵活应用是关键。
基本上就这些。
