带路径压缩与按秩合并的并查集是高效处理动态图连通性查询与合并的经典数据结构，通过parent数组维护父节点、rank数组优化树高，find实现路径压缩，unionSet按秩合并，isConnected封装连通判断。

如果您需要在 C++ 中高效判断动态图中节点的连通性，并支持频繁的合并与查询操作，则带路径压缩的并查集是一种经典且实用的数据结构。以下是该算法的完整实现逻辑与源码说明：

一、基于数组的父节点与秩数组初始化

并查集底层使用两个数组：parent[] 存储每个节点的直接父节点，rank[] 记录以该节点为根的子树近似高度（用于按秩合并）。初始化时，每个节点独立成集，parent[i] = i，rank[i] = 0。

1、声明全局或类内私有成员数组：int parent[N]; int rank[N]; 其中 N 为最大节点数。

2、编写初始化函数：遍历 0 到 N-1，执行 parent[i] = i; rank[i] = 0;

3、确保所有节点索引在合法范围内，索引必须从 0 开始连续编号，不可跳号或使用负值。

二、带路径压缩的查找根节点操作

find 函数用于定位某节点所属集合的根节点，同时在递归回溯过程中将路径上所有经过节点的 parent 直接指向根，显著降低后续查询时间复杂度。

1、定义 int find(int x) 函数。

2、若 parent[x] != x，则执行 parent[x] = find(parent[x])，实现路径压缩。

3、返回 parent[x]；此步必须在压缩后返回，否则压缩无效。

三、按秩合并的 union 操作

unionSet 函数将两个节点所在集合合并，优先将秩较小的树挂到秩较大的树下，避免深度无序增长，配合路径压缩可使单次操作接近常数时间。

1、计算 rootX = find(x)，rootY = find(y)。

2、若 rootX == rootY，直接返回，无需重复合并已连通节点。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

3、若 rank[rootX]

4、若 rank[rootX] > rank[rootY]，令 parent[rootY] = rootX。

5、若 rank[rootX] == rank[rootY]，任选其一作为新根，并将其 rank 值加 1。

四、连通性判定接口封装

isConnected 函数提供语义清晰的连通性判断入口，仅需传入两节点编号，内部调用 find 进行根节点比对，返回布尔结果。

1、定义 bool isConnected(int x, int y) 函数。

2、返回 find(x) == find(y) 的比较结果。

3、该函数不修改任何 parent 或 rank 值，仅为只读查询。

五、完整可运行源码片段

以下为标准 C++11 及以上兼容的最小可编译示例（含头文件与主函数调用示意）：

1、包含必要头文件：#include #include

2、定义常量 const int MAXN = 100005;

3、声明全局数组：std::vector parent(MAXN), rank(MAXN);

4、在 main 函数前完成 init()、find()、unionSet()、isConnected() 四个函数定义；init() 必须在首次 union 或 find 前调用。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！