路径压缩需递归返回时自底向上更新父指针，仅一次递归不赋值会导致中间节点未压缩；union前必须判连通以避免冗余操作和破坏按秩合并；路径压缩与按秩合并可共存，rank仅作合并决策上界，不随压缩更新。
为什么路径压缩不能只靠递归一次就完事
路径压缩的核心目标是让查找过程中经过的所有节点直接指向根节点，而不是仅仅把查询节点连到根上。如果只做一次 find(x) 递归后简单赋值 parent[x] = find(parent[x])，但没在返回前更新当前层的 parent[x]，就会漏掉中间节点——尤其在多层嵌套时，只有最深那一层被压，上面几层仍维持旧链。
正确做法是在递归返回时「自底向上」重连：先拿到根，再把当前节点的父指针设为该根。这样整条路径上的每个节点都会在各自函数栈帧中完成跳转。
- 错误写法：
return parent[x] == x ? x : find(parent[x]);（没更新parent[x]） - 正确写法：
return parent[x] = (parent[x] == x ? x : find(parent[x])); - 注意：必须用赋值表达式参与 return，否则
parent[x]不会被修改
union 操作里要不要检查是否已连通
不做检查也能工作，但会徒增一次不必要的 find 调用和潜在的父指针修改开销。更关键的是，如果后续依赖「合并次数」或「连通分量数」统计，未判重会导致计数错误。
标准实现中，unionSets(a, b) 应该先 find(a) 和 find(b) 得到根，再比对是否相等。相等就直接返回，不执行任何指针操作。
- 避免冗余操作：两次
find+ 一次比较，远快于一次find+ 一次赋值 + 可能触发的树高更新 - 影响按秩合并：若跳过判等，可能把小树挂到大树下，破坏秩平衡，使后续
find平均变慢 - 典型错误：写成
parent[find(a)] = find(b);而不先判断，导致同一集合内反复合并
按秩合并（union by rank）和路径压缩能否共存
可以，而且应该共存。路径压缩优化查找时间，按秩合并控制树高增长，二者解决不同维度的问题，叠加后并查集的单次操作均摊时间复杂度可达 O(α(n))（阿克曼反函数，实际中 ≤ 4）。
但要注意：路径压缩会改变节点深度，所以「秩（rank）」不再表示真实高度，而是一个上界估计值。因此 rank 数组只在合并时用于决策谁当父节点，不参与查找逻辑。
-
rank[i]初始全为 0；每次合并两个同秩根时，被选为子树的那个根对应rank不变，父节点的rank加 1 - 路径压缩不修改任何
rank值，哪怕某个节点被压缩后实际深度变成 1，它的rank还是原来那个上界 - 误用风险：有人试图在路径压缩中同步更新
rank，这不仅无意义，还会破坏按秩合并的语义
C++ 完整实现中容易被忽略的细节
完整可运行代码的关键不在算法主干，而在初始化、边界处理和类型安全。比如数组索引从 0 还是 1 开始、rank 和 parent 是否用 vector 动态分配、是否支持负数索引等，都会影响实操稳定性。
以下是最简但健壮的实现要点：
- 用
vector<int> parent, rank;</int>，下标 0 ~ n-1 对应节点 0 ~ n-1，避免偏移计算出错 - 构造函数中显式调用
iota(parent.begin(), parent.end(), 0);初始化，别手写循环漏掉某处 -
find必须声明为const不可行——因为要改parent[x]，所以成员函数不能加const - 如果节点编号不连续（如 ID 是字符串或大整数），得换哈希表实现，此时路径压缩依然有效，但
rank维护成本上升，通常改用 size 合并更稳妥
真正难的不是写出 find 和 unionSets，而是确保初始化没越界、合并时没把无效索引传进去、以及在多线程场景下意识到它默认不安全——这些地方不出错，算法才真的算“可用”。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
