路径压缩需在回溯时更新父指针或迭代重连，仅递归找根不修改父节点无法实现压缩；union_by_rank适合理论复杂度要求场景，union_by_size更直观且支持大小统计；初始化必须显式设置parent、rank/size，避免越界与未定义行为。
为什么路径压缩不能只靠递归一次就完事
路径压缩的核心目标是让查找操作后，从任意节点到根的路径上所有节点都直接指向根。但很多人写成 find(x) { return parent[x] == x ? x : find(parent[x]); }，这没做压缩——只是递归找根，没改父节点。真正压缩必须在回溯时重连，或者用迭代方式边查边改。
实操建议：
- 递归写法必须在返回前执行
parent[x] = find(parent[x])，而不是只返回find(parent[x]) - 迭代写法更易理解且无栈溢出风险：先走到底找到根，再从原节点开始逐个挂到根下
- 若数据规模超 10⁵，递归可能爆栈，尤其未开启编译器尾递归优化时
union_by_rank 和 union_by_size 选哪个更稳
合并策略直接影响树高，进而影响 find 的平均耗时。两者都比朴素合并（随便认爹）强，但适用场景略有不同。
实操建议：
-
union_by_rank维护的是“秩”（近似高度上界），不等于真实高度，适合强调理论复杂度（均摊 O(α(n))）的场景 -
union_by_size记录子树节点数，逻辑更直观，且在需要统计连通分量大小时天然可用，无需额外遍历 - 二者不能混用；若同时需要 size 和 rank，优先存 size——rank 可由 size 推出（log₂(size)），但反之不成立
如何避免 find 和 union 中的越界与未初始化错误
并查集常作为工具嵌入更大逻辑，parent 和 rank/size 数组若未正确初始化，运行时可能静默出错或触发 std::out_of_range（如用 vector::at()）。
常见错误现象：
- 用
vector<int> parent(n)</int>但索引从 1 开始，导致parent[0]被忽略、parent[n]越界 - 声明
vector<int> rank(n)</int>却忘了初始化为 0，某些平台内存残留非零值，造成合并逻辑错乱 - 动态扩容后未同步更新
parent和辅助数组长度
实操建议：
- 构造函数中统一用
parent.resize(n); std::iota(parent.begin(), parent.end(), 0); - 辅助数组一律显式初始化：
rank.assign(n, 0)或size.assign(n, 1) - 若支持动态加点（如离线读入未知总数），改用
map<int int></int>存 parent，但注意哈希冲突和性能损失
连通性判定别直接比根，小心未完全压缩的中间态
有人写 connected(a, b) { return find(a) == find(b); } 看似正确，但如果 find 实现有缺陷（比如只压缩了 a 的路径，b 的路径仍是长链），两次 find 返回的“根”可能不同——即使本应连通。
这通常暴露在混合使用路径压缩和按秩合并的代码里：某次 union 后，部分节点尚未被 find 触发压缩。
实操建议：
-
connected必须调用两次find，且每次调用都保证完整压缩，不可缓存或跳过 - 不要依赖
parent[a] == parent[b]判连通——这是典型错误，父节点相同不等于根相同 - 调试时可在
find入口加断言：assert(parent[x] >= 0 && parent[x]
路径压缩不是银弹，它和合并策略、初始化、索引习惯绑在一起。少一个环节出问题，整个连通性判定就不可靠——尤其在线上系统里，这种 bug 往往只在特定数据分布下才浮现。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
