路径压缩使find从O(n)降至O(α(n))，需递归或迭代更新整条路径；按秩合并控深度，按大小合并适统计规模；注意索引偏移、栈溢出及初始化。
为什么 find 里不路径压缩就容易超时
不做路径压缩的并查集，find 最坏退化成 O(n) 链表遍历，尤其在大量查询+合并混合操作时，总时间可能从 O(α(n)) 暴涨到 O(n²)。路径压缩本质是「边查边平铺」：每次 find(x) 返回根的同时，把 x 到根路径上所有节点的 parent 直接指向根。
常见错误是只改了 x 的父节点，没递归更新整条路径；或压缩逻辑写在递归外层，导致部分节点漏压。
- 必须用递归写法（或显式栈模拟），确保回溯时逐级重连
- 压缩后不能破坏当前合并关系——只改
parent，不动rank或size - 别在
union里手动调用find后再压缩，那会重复压缩，浪费且易错
union 该用按秩合并还是按大小合并
两者都可配合路径压缩使用，但语义和适用场景不同：rank 是上界估计（树高），适合强调最坏深度控制；size 是子树节点数，适合需要统计连通分量规模的场景（如题目要求“最大连通块大小”）。
按秩合并中，rank 只在两棵树高度相等时才 +1，否则不更新；按大小合并则直接把小树挂到大树下，size[root] 累加即可。两者都不影响路径压缩逻辑。
- 若只关心连通性判定，二者性能几乎无差别，选哪个看后续是否需复用字段
- 混用
rank和size字段会导致逻辑混乱，初始化和更新必须严格对应 - 注意：路径压缩后树高失去意义，
rank不再等于真实高度，仅作合并策略参考
如何避免 find 递归爆栈或写错边界
小数据量下递归 find 很简洁，但 n > 1e5 且链式结构严重时，递归深度可能超系统栈限制。此时应改用迭代写法，手动维护路径节点列表再统一更新父指针。
另一个高频错误是忘记处理自环：当 parent[x] == x 时必须立即返回，否则无限递归或数组越界。
- 迭代版核心：先向上跳到根，记录路径上所有节点，再遍历路径设
parent[node] = root - 务必检查
x是否在合法索引范围内（尤其输入含 1-based 编号时） - 不要在
find中修改rank或size，那是union的职责
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 递归压缩
}
return parent[x];
}
初始化与索引偏移容易被忽略的细节
很多题输入节点编号从 1 开始，但数组习惯 0-based。如果直接用输入值当索引，轻则越界访问，重则覆盖关键内存（如把 parent[0] 当作哨兵却未初始化）。
另外，并查集不是万能容器：它只维护等价关系，无法还原具体连接边、不能高效查某点邻居、也不支持删边操作。如果题目后续要输出连通块内所有元素，得额外用 vector<vector>></vector> 按根归类。
- 初始化必须覆盖全部可能节点：若最大编号是 n，数组长度至少为 n+1，且
parent[i] = i要跑满 - 若用 vector，别忘了
resize(n+1)，否则push_back会导致索引错位 - 多组测试用例时，记得重置
parent、rank/size数组，别复用旧状态
实际写的时候，路径压缩和按大小合并配对最省心；真遇到栈溢出，换迭代 find 几行就搞定；至于编号偏移，加个 -1 还是开大一格，动手前花十秒确认清楚，比调试十分钟强。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
