c++中如何实现并查集_c++并查集实现方法

答案是C++中并查集通过parent和rank数组实现，支持find和unionSet操作，结合路径压缩与按秩合并优化效率。初始化时每个元素自成一集，find查找根节点并压缩路径，unionSet按秩合并两集，isConnected判断连通性，适用于Kruskal算法等场景。

在C++中实现并查集（Union-Find Set），也叫不相交集合（Disjoint Set），主要用于高效处理集合的合并与查询问题。典型应用场景包括连通分量判断、最小生成树中的Kruskal算法等。

基本结构与核心操作

并查集主要支持两个操作：

• find(x)：查找元素x所在集合的代表（根节点）
• unionSet(x, y)：将包含x和y的两个集合合并

为了提高效率，通常结合“路径压缩”和“按秩合并”两种优化策略。

数组实现父节点与秩

使用两个数组：

立即学习“C++免费学习笔记（深入）”；

• parent[]：记录每个节点的父节点
• rank[]：记录每棵树的深度（用于按秩合并）

初始化时，每个元素的父节点是自己，秩为0。

代码实现示例

以下是完整的C++实现：

// 并查集类实现
class UnionFind {
private:
vector parent;
vector rank;
public:
// 构造函数，初始化n个独立元素
UnionFind(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// 判断两个元素是否在同一集合
bool isConnected(int x, int y) {
return find(x) == find(y);
}
};

使用示例

如何在主函数中使用这个并查集：

int main() {
UnionFind uf(5); // 创建5个元素的并查集
uf.unionSet(0, 1);
uf.unionSet(1, 2);
uf.unionSet(3, 4);
cout

基本上就这些。路径压缩让find接近O(1)，按秩合并控制树高，整体效率非常高。