c++怎么实现一个并查集（Disjoint Set Union）_C++实现Union-Find并查集算法详解-C++-PHP中文网

c++怎么实现一个并查集（Disjoint Set Union）_C++实现Union-Find并查集算法详解

下次还敢

发布： 2025-10-31 09:44:02

原创

470人浏览过

并查集通过Find和Union操作管理分组，支持路径压缩与按秩合并优化，用于高效处理连通性问题。

c++怎么实现一个并查集（disjoint set union）_c++实现union-find并查集算法详解

并查集（Disjoint Set Union，简称 DSU 或 Union-Find）是一种高效管理元素分组的数据结构，支持快速合并集合与查询元素所属集合。它常用于处理无向图的连通性问题，比如判断两个节点是否连通、求连通分量个数等。

基本结构与操作

并查集主要包含两个核心操作：

Find(x)：查找元素 x 所在集合的代表（根节点）
Union(x, y)：将元素 x 和 y 所在集合合并

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

基础实现代码

// 并查集类实现 class UnionFind { private: vector parent; // 父节点数组 vector rank; // 秩（树的高度上界） public: // 构造函数，初始化每个元素为独立集合 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]++; // 高度相等时，合并后高度+1 } } // 判断两个元素是否在同一集合 bool connected(int x, int y) { return find(x) == find(y); } };