c++中如何实现并查集_c++并查集实现方法-C++-PHP中文网

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

穿越時空

发布： 2025-09-27 21:14:01

原创

523人浏览过

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

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

在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); } };