路径压缩必须在find返回根后更新父指针，递归版先递归再赋值，迭代版需两次遍历（先找根再重连），避免跳步压缩或提前修改导致链断、指向错误。
路径压缩怎么写才不破坏并查集的语义正确性
路径压缩不是简单地把所有子孙节点都连到根，而是要在 find 过程中「边查边改」：每次递归返回时，把当前节点的父指针直接指向递归得到的根。这样既保证了后续查询更快，又不会影响任何已有合并操作的逻辑。
常见错误是手动循环改父指针却漏掉中间某层，或者在非递归实现里没保存原始根——结果导致部分节点指向错误根，union 判定失准。
- 必须在
find返回后才更新parent[x]，不能在递归调用前改 - 非递归版本需先走到底拿到根，再从原节点向上遍历重连，否则容易链断
- 如果同时用按秩合并（
rank），路径压缩后rank值不再严格代表树高，但不影响正确性——别拿它做判断依据
带路径压缩的 find 函数典型实现与陷阱
最简递归写法可靠，但深树可能栈溢出；迭代写法省栈空间，但容易在「二次遍历」时搞错节点顺序。
这是安全的递归版本：
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 先递归找根，再压缩
}
return parent[x];
}
迭代版关键在两次遍历：第一次找根，第二次从起点沿原链路上去改父指针：
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
- 别在迭代版里用
parent[x] = parent[parent[x]]类似跳步压缩——会漏节点 - 如果用了
vector<int></int>存parent，注意下标从 0 开始，别越界访问parent[-1] - 调试时可加 assert(
parent[x] >= 0 && parent[x] ) 防野指针
路径压缩 + 按秩合并是否真有必要共存
单独路径压缩已让均摊时间接近 O(α(n))，按秩合并（或按大小合并）主要起辅助作用：避免路径压缩失效场景下的退化（比如反复 union 同一对手）。两者合用才是工业级稳健方案。
按秩合并的 union 要注意：只比较根的 rank，不是任意节点的；合并后仅当两子树秩相等时，新根秩才 +1。
- 用
size替代rank更直观（按大小合并），但需在union前确保传入的是两个根，否则size[x]无意义 - 路径压缩不改
size或rank，所以它们只在根节点上有效——其他位置的值可视为废弃 - 如果业务只要判定连通性、不关心合并方向，可以只用路径压缩；但若要支持「撤销 union」或统计连通分量大小，按大小合并更易维护
实际项目中容易被忽略的边界点
很多线上 bug 不是算法错，而是初始化或索引没对齐。比如图节点编号从 1 开始，但数组开了 parent[n] 却用 parent[i] 直接存，结果 i = n 时越界；或者并查集生命周期管理混乱，对象析构后还调 find。
- 构造函数里务必初始化
parent[i] = i，且rank[i] = 0或size[i] = 1—— 漏掉一个就全乱 - 多线程环境必须加锁，或改用原子操作（C++20
std::atomic<int></int>），别信“读多写少就没事” - 调试时打印几个关键节点的
find(x)结果，比单步跟递归更高效；重点看是否所有同分量节点返回同一个根
路径压缩真正难的不是代码几行，而是想清楚「谁该指向谁」以及「什么时候改」——改早了，链断；改晚了，没压；改错了，整个连通关系崩掉。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
