路径压缩必须与按秩合并联用，否则树高统计失效致union退化为O(n)；二者结合使find均摊时间达O(α(n))，α(n)≤4；递归路径压缩更安全，需parent[x] = find(parent[x])一步完成。
为什么路径压缩必须和按秩合并一起用
单独做路径压缩会让树高失去统计意义，后续 union 操作无法可靠判断哪棵树更矮，导致最坏情况退化成 O(n)。按秩合并（rank）本身不保证树高严格对数，但和路径压缩配合后，单次 find 均摊时间能稳定在接近 O(α(n)) —— 这不是常数，但对所有实际规模的 n（哪怕宇宙原子数级），α(n) ≤ 4。
实操建议：
- 初始化每个节点
parent[i] = i，rank[i] = 0 -
union时只比较rank，不比较当前深度；rank仅在两子树高度相等时才 +1 -
find中递归调用后立即更新parent[x]，不是返回后再赋值
路径压缩的递归写法比迭代更安全
迭代实现容易漏掉根节点的父指针更新，或在更新过程中破坏中间状态。递归天然保证“先触底、再回溯、逐层挂载”，逻辑清晰且不易出错。
典型错误现象：find(5) 返回了正确根节点，但 parent[5] 仍指向旧父节点，下次查询没收益。
关键代码片段：
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // ← 必须这行在 return 前，且赋值给 parent[x]
}
return parent[x];
}
注意：parent[x] = find(parent[x]) 这句不能拆成两步，也不能写成 x = find(parent[x]) 后再赋值 —— 那样就丢失了原始 x 的引用。
按秩合并中 rank 不是高度，只是上界估计
rank 数组记录的是该节点作为根时，其子树的**最大可能高度**（即“秩”），不是实时树高。路径压缩会压平路径，但不修改 rank —— 这没问题，因为 rank 只用于 union 决策，不参与 find 计算。
使用场景：当你要支持动态连通性查询（如网络节点连通、图的边添加后判环），又不想引入额外数据结构（比如 DFS 标记数组），这个组合就是最简可靠方案。
性能影响：
- 内存多开一个
rank数组，O(n) 空间无额外负担 - 构造函数初始化
rank比全填 -1 或 1 更稳妥，避免误判 - 如果确定永远只做
find不做union，可省略rank，纯路径压缩也够用
初始化和边界检查最容易被忽略的两个点
一是下标越界：C++ 数组/向量从 0 开始，但题目输入节点编号常从 1 开始，parent 和 rank 容量必须设为 n+1，否则 parent[n] 越界；二是未初始化：用 vector 时若只声明不 resize，后续访问 parent[x] 是未定义行为。
实操建议：
- 构造函数中显式
parent.resize(n + 1)和rank.resize(n + 1, 0) - 加一层断言：
assert(x >= 1 && x 在find/union开头（调试期） - 如果节点编号稀疏（比如只有 1、100、10000），别硬套数组，改用
unordered_map存parent，但要接受常数级开销
复杂点在于：路径压缩让树结构“失真”，你不能再依赖父子关系做任何遍历或路径重建；它只为快速回答“是否同属一集”而存在 —— 这个目的之外的功能，得换别的结构。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
