路径压缩优化并查集查找操作的时间复杂度，通过在find过程中让路径上所有节点直接指向根节点来“拍平”树链；需配合按秩或按大小合并才能实现近乎o(α(n))的均摊性能。
路径压缩到底在优化什么
并查集的查找操作本质是“顺着父指针一路向上，直到根节点”。如果树退化成链状，比如 1→2→3→4→0（0 是根），查 1 就要跳 4 次。路径压缩就是让这一路上的节点，在查找过程中直接认根为父，把长链“拍平”。一次 find(1) 后，1、2、3 都可能直接指向 0，下次再查它们就只需 1 步。
两种常用压缩写法及适用场景
递归写法最简洁，适合理解逻辑和教学场景：
- 代码模式：if (x != parent[x]) parent[x] = find(parent[x]); return parent[x];
- 效果：整条路径上的所有节点在本次返回前全部指向根，压缩彻底
- 注意点：递归深度受数据规模限制，超大规模（如 n > 10⁶）慎用，可能栈溢出
迭代写法更可控，适合工程落地：
- 代码模式：先遍历到根，再回溯把路径上每个节点的父设为根
- 效果：同样实现全路径压缩，且无递归开销
- 优势：内存稳定，配合按秩合并时更容易调试和复用
单独路径压缩还不够，必须配按秩/按大小合并
只做路径压缩，不能阻止树在 union 时越长越高。例如反复把大树挂到小树下，虽然每次 find 都会压，但下一次 union 又可能拉长新分支。真正高效需要双保险：
- 按秩合并（rank）：记录每棵树的近似高度，总是把 rank 小的根连向 rank 大的根；rank 相等时才让一方 rank +1
- 按大小合并（size）：记录每棵树的节点数，总是把节点少的树挂到节点多的树下
- 关键细节：启用任一合并策略后，路径压缩仍可独立开启，二者正交、互补，共同将均摊时间复杂度压到近乎 O(α(n))（反阿克曼函数，实际中 ≤ 4）
实战中容易踩的坑
写对 find 不等于用对并查集。常见疏漏包括：
- union 前没调 find：直接 parent[a] = b 是错的，必须 parent[find(a)] = find(b)，否则挂的是叶子而非根
- 初始化遗漏：parent[i] = i 必须全覆盖，尤其数组下标从 1 开始时，别漏掉 index 0 或末尾
- 压缩与合并顺序混淆：路径压缩只影响 find；合并策略只影响 union；两者不要混进同一个函数里强行耦合
- 查询时忘记 find：判断是否同集合，必须用 find(a) == find(b)，不能用 parent[a] == parent[b]，后者只反映直系父子关系
