应采用安全递归版find并显式分离求根与赋值：先递归获取真实根节点，再统一更新当前节点父指针；声明std::vector parent(n+1)，初始化循环for(int i=1;i

如果您在实现C++并查集时发现连通性判定变慢、树高失控或多次查询性能骤降，则可能是路径压缩未正确触发、按大小合并缺失或find逻辑存在求值顺序隐患。以下是解决此问题的步骤：

一、采用安全递归版find并显式分离求根与赋值

该方法确保每次find调用均完成完整路径压缩，避免C++求值顺序未定义导致的parent[x] = find(parent[x])语义失效。核心是先递归获取真实根节点，再统一更新当前节点父指针，杜绝中间节点残留旧父引用。

1、声明parent数组为std::vector parent(n + 1)，索引范围覆盖1..n。

2、初始化循环：for (int i = 1; i

3、定义find函数：int find(int x) { if (parent[x] != x) { int root = find(parent[x]); parent[x] = root; return root; } return x; }

4、调用find(x)时，必须确保返回值被使用，且parent[x]在return前已被设为root。

二、使用迭代双遍历find替代递归以规避栈溢出与求值陷阱

该方法彻底消除递归调用栈深度限制和编译器求值顺序不确定性，通过两次独立遍历精确控制路径上每个节点的父指针重定向，适用于超大规模节点（如10⁵以上）场景。

1、声明parent数组同上，保证内存连续且下标合法。

2、定义find函数：int find(int x) { int root = x; while (root != parent[root]) root = parent[root]; while (x != root) { int next = parent[x]; parent[x] = root; x = next; } return root; }

3、第一遍while循环严格定位root，第二遍while循环逐个修正路径节点，漏掉第二遍将导致路径压缩不彻底，复杂度退化为O(n)。

三、强制union前执行双find并比对根节点

该方法防止重复合并已连通集合，保护rank/size启发式有效性，并确保连通分量计数准确。直接比较parent[a]与parent[b]不可靠，必须通过find获得压缩后的真实根。

1、对输入边(u, v)，先执行int ru = find(u); int rv = find(v);

2、立即判断if (ru == rv) return; 避免后续无效操作。

C++14

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

下载

3、仅当ru != rv时进入合并逻辑，禁止跳过find直接使用原始u、v参与parent赋值。

四、选用size启发式合并而非rank，配合路径压缩共存

该方法利用size始终反映真实子树规模的特性，避免路径压缩后rank失真问题，同时支持后续直接读取连通分量大小。size与路径压缩协同可逼近O(α(n))均摊复杂度。

1、额外声明std::vector size(n + 1, 1); 初始化时size[i] = 1对应每个独立节点。

2、合并时比较size[ru]与size[rv]，将size较小的根挂至size较大的根下。

3、执行parent[small_root] = large_root; 并更新size[large_root] += size[small_root];

4、非根节点的size值永不修改，仅新根的size被累加。

五、结构体内聚存储parent与size以提升CPU缓存命中率

该方法将关联数据打包进单个struct，使vector在遍历时更大概率落入同一cache line，减少cache miss次数，尤其在高频find/union混合操作中效果显著。

1、定义struct Node { int parent; int size; };

2、声明vector dsu(n + 1);

3、初始化循环：for (int i = 1; i

4、find与union操作中统一通过dsu[x].parent和dsu[x].size访问，避免拆分为两个独立vector导致CPU需多次加载不相邻内存块。

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