路径压缩必须用递归或双遍历迭代实现，确保每层返回前更新父指针；union前须双find判等；按大小合并比按秩更准确，需配合路径压缩使用。

如果您在C++中实现带路径压缩的并查集时发现查询效率未达预期，或出现栈溢出、压缩失效、合并错误等现象，则很可能是路径压缩与合并策略未协同生效。以下是解决此问题的步骤：

一、采用安全递归版find实现路径压缩

该方法利用递归回溯天然完成逐层父指针更新，避免C++求值顺序未定义导致的压缩失败。关键在于先获取根节点再显式赋值，确保每个访问节点直连根。

1、定义整型数组或vector parent存储父节点，初始化时令parent[i] = i；

2、编写find函数：若parent[x] != x，则先调用find(parent[x])获取真实根节点root；

3、将parent[x]显式赋值为root；

4、返回root而非parent[x]（防止未更新前返回旧值）。

二、使用双遍历迭代版find规避栈溢出风险

该方法不依赖递归调用栈，适用于超大集合或深度链状结构，通过两次独立遍历分别定位根节点和批量更新路径，彻底消除栈溢出与求值陷阱。

1、声明int root = x，循环执行root = parent[root]直至root == parent[root]，得到根节点；

2、重置x为原始输入值，进入第二循环：当x != root时，保存原父节点int next = parent[x]；

3、将parent[x]设为root；

4、令x = next，继续处理下一节点，直至整条路径更新完毕。

三、强制在union前执行双find并判等

直接对原始输入x、y执行parent[find(x)] = find(y)会破坏森林结构，必须先分离逻辑：先获取各自根节点，再判断是否已连通，仅在不连通时才执行合并操作，否则污染树高并干扰size/rank统计。

1、调用int rx = find(x)和int ry = find(y)，获取x与y所在集合的真实根；

C++14

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

下载

2、判断rx == ry，若成立则立即返回，不进行任何父指针修改；

3、若rx != ry，进入合并逻辑，禁止跳过此判等步骤；

4、后续仅基于rx、ry操作，杜绝使用原始x、y参与parent赋值。

四、配合按大小合并确保均摊复杂度逼近O(α(n))

仅路径压缩无法突破O(log n)最坏均摊复杂度，必须引入按大小合并策略——将小集合根挂至大集合根下，抑制树高增长，使路径压缩效果可持续累积。size比rank更可靠，因其不受压缩影响且可直接用于查询连通分量大小。

1、维护vector size，初始化时size[i] = 1；

2、在union分支中，比较size[rx]与size[ry]；

3、若size[rx]

4、否则执行parent[ry] = rx，并更新size[rx] += size[ry]；

5、注意：仅更新新根对应的size值，非根节点的size字段永不修改。

五、严格初始化与索引边界控制

越界访问或未初始化会导致段错误、虚假连通或逻辑错乱。必须显式覆盖全部有效节点索引范围，尤其当输入编号从1开始时，需统一映射至0-based或预留n+1空间。

1、声明vector parent(n + 1), size(n + 1, 1)；

2、使用for循环从i = 1到i

3、确保所有输入节点编号在1~n范围内，读入后立即执行a--、b--转换；

4、禁止使用map模拟稀疏节点——会破坏O(1)随机访问前提，导致find平均变慢。

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