路径压缩必须用递归，因其天然具备回溯时机，可在返回途中将路径上所有节点直接指向根；非递归while循环仅查找根而未更新父指针，导致无压缩效果。
为什么 find 必须用递归才能正确路径压缩？
非递归写法（比如 while 循环 + 二次遍历）看似省栈，但会漏压中间节点。路径压缩的本质是「在回溯时把沿途所有父指针直接连到根」，只有递归天然具备这个回溯时机。
常见错误是写成：
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
这完全没压缩——只是找根。正确写法必须边查边改：
-
parent[x] = find(parent[x])是关键：先递归拿到根，再把当前节点挂上去 - 必须返回
parent[x]而不是x，否则压缩失效 - 若担心栈溢出（比如 n > 1e6），可加迭代版备选，但默认用递归更安全
unionSet 里按秩合并（rank）和按大小合并（size）怎么选？
两者都保证树高 ≤ log n，但语义不同：rank 是上界估计，size 是真实子树节点数。实际中 size 更直观，且能顺便支持「连通分量大小查询」需求。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 用
size合并时，总是把小树的根指向大树的根：if (size[rootA] - 合并后记得更新：
size[rootB] += size[rootA]; - 如果只关心连通性、不关心分量大小，
rank省一点内存（int 改 short），但差别微乎其微 - 别混用：同一份代码里不要一会儿比
rank，一会儿比size
初始化时 parent[i] = i 和 size[i] = 1 容易漏哪几个？
最常漏的是索引越界或未初始化全部元素。比如用 vector 但只 reserve 没 resize，或数组下标从 1 开始却忘了初始化 parent[0]。
典型坑点：
-
vector<int> parent(n)</int>初始化为 0，但 0 不等于下标——必须显式赋值：for (int i = 0; i - 如果节点编号是离散的（比如输入含 100、200、500），不能直接开
n大小数组，得先离散化或改用unordered_map -
size数组必须全初始化为 1；设成 0 会导致合并时误判“空树”，引发逻辑错
判定连通性时，为什么不能直接比较 parent[a] == parent[b]？
因为路径压缩只发生在 find 过程中，parent[a] 可能还指着旧父节点，根本不是根。直接比父节点等于拿两个中间状态做判断，必然出错。
必须统一走 find：
- 正确：
find(a) == find(b) - 错误：
parent[a] == parent[b]、find(a) == b、a == find(b) - 如果频繁查连通性，可以缓存
find结果避免重复调用，但不能跳过find - 注意：
find有副作用（改parent），所以多次调用是安全的，但不能假设它“只读”
路径压缩和按秩/大小合并是耦合优化：单独用任一个，复杂度只是均摊 O(log n)；两者合用才达到均摊 O(α(n))。很多人调通了功能就停在这一步，但真正卡常或处理 1e6+ 查询时，漏掉其中一个就会慢几倍——尤其在链式数据（如 1-2-3-…-n）上差异极明显。
