路径压缩真正生效需在find中更新父节点：递归写法为parent[x] = find(parent[x])，非递归需两遍遍历；仅路径压缩最坏单次find仍为O(log n)，建议配合按秩合并；初始化用std::iota更优，判定连通性须确保x、y均完成路径压缩。
路径压缩在 find 中怎么写才真正生效
路径压缩不是“调用一次 find 就自动优化所有祖先”，它只作用于当前查询路径上的节点。常见错误是写成非递归但没做二次赋值，或者递归中漏掉回溯赋值：
- 错误写法：
return parent[x] == x ? x : find(parent[x])—— 没更新parent[x]，压缩无效 - 正确递归写法：
return parent[x] == x ? x : parent[x] = find(parent[x])—— 关键是赋值动作必须发生在 return 前 - 非递归写法需两遍遍历：第一遍找根，第二遍从原
x开始逐级设为根，否则中间节点仍指向旧父节点
union 里要不要按秩合并？不合并会怎样
单独路径压缩已能将均摊复杂度压到接近 O(α(n))，但若只靠压缩、不做按秩/按大小合并，最坏单次 find 仍可能退化到 O(log n)（比如反复 union 链状结构）。实际中建议保留按秩合并，因为：
- 代码增量极小：只需维护
rank或size数组，union时比较后决定谁当父节点 - 和路径压缩正交互补：按秩控制树高，压缩加速后续查找，两者叠加才能稳定达到反阿克曼级别性能
- 不合并时，大量
union后再密集find，实测在 10⁵ 级数据下慢 2–3 倍
初始化和内存布局影响访问速度
并查集本质是数组随机访问，缓存友好性比算法本身更早成为瓶颈。常见低效点：
- 用
std::vector<int></int>存parent和rank是 OK 的，但若拆成两个 vector（如vector<int> parent, rank</int>），CPU cache line 可能无法同时载入关联数据 - 更优做法：用 struct 打包，如
struct Node { int parent; uint8_t rank; }，然后vector<node></node>—— 减少 cache miss - 初始化别用循环赋值
parent[i] = i：现代编译器对std::iota优化更好，且语义清晰
连通性判定别直接比根，小心未压缩残留
判定 x 和 y 是否连通，不能简单写 find(x) == find(y) 然后认为“结果可靠”——如果之前只对 x 调过 find，而 y 的路径还没压缩，下次查 y 还可能变慢。真正健壮的判定逻辑应：
立即学习“C++免费学习笔记（深入）”；
- 总是先执行
find(x)和find(y)，让两者路径都压缩到位 - 再比较返回值；或更进一步，把比较封装进函数，避免使用者漏掉压缩步骤
- 注意：某些竞赛题会故意构造数据，在未压缩路径上卡时间，仅靠“理论均摊快”扛不住
路径压缩不是银弹，它依赖每次查询都触发更新。漏掉一次 find，就可能让某个分支长期保持深链状态。
