C++实现带路径压缩并查集算法的连通性快速判定逻辑与路径优化源码【源码】-C++-PHP中文网

应使用带路径压缩与按秩合并的并查集：初始化parent[i]=i、rank[i]=0（数组长n+1防越界）；合并时先find得根再按秩挂接；判连通唯一正确写法是if(find(a)==find(b))。

c++实现带路径压缩并查集算法的连通性快速判定逻辑与路径优化源码【源码】

要在C++中高效判定动态图中任意两点是否连通，并支持频繁合并操作，必须避免朴素遍历或未压缩的树查找——否则一次find可能退化为O(n)，十万节点下查询直接卡死。

初始化并查集结构

声明parent和rank数组，大小必须严格匹配节点编号范围；若输入节点从1开始编号（如边列表含1 2、2 3），则数组长度至少为n+1，否则parent[n]越界访问将导致未定义行为。

用循环显式初始化每个节点：parent[i] = i，rank[i] = 0；【不能依赖全局变量零值或vector默认构造】，多次复用同一DSU实例时，未重置的parent值会残留旧状态，引发虚假连通。

若使用vector，写成vector parent(n + 1), rank(n + 1, 0);再for (int i = 1; i

实现带路径压缩的find函数

方法一（递归，推荐默认使用）：
定义int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
这行parent[x] = find(parent[x])是核心：先递归到底拿到根，再把当前x的父指针直接连到根，回溯过程天然完成整条路径压缩。

方法二（迭代，防栈溢出）：
先用while定位root：int root = x; while (root != parent[root]) root = parent[root];
再第二遍遍历路径：while (x != root) { int next = parent[x]; parent[x] = root; x = next; }
返回root。
【漏掉第二遍遍历=只找根不压缩，等同于没写】

C++14

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

下载

按秩合并unionSet操作

第一步：调用rootX = find(x)、rootY = find(y)，获取两节点所在集合的真正根；
第二步：若rootX == rootY，立即return，跳过后续——重复合并同一集合会错误抬高rank，破坏树高控制；
第三步：比较rank[rootX]与rank[rootY]；
第四步：若rank[rootX] 第五步：若rank[rootX] > rank[rootY]，执行parent[rootY] = rootX；
第六步：若相等，任选其一为新根（如parent[rootY] = rootX），并执行rank[rootX] += 1。