路径压缩正确写法是递归中parent[x] = find(parent[x])，确保沿途节点父指针直连根且不破坏连通性；需配合初始化、返回根节点、避免重复find等要点。
路径压缩怎么写才不破坏并查集语义
路径压缩的本质是在 find 过程中把沿途所有节点的父指针直接指向根，但必须确保「压缩后仍能正确反映连通性」。常见错误是只改了当前节点的 parent，没递归更新上层——这会导致后续 find 返回错误根节点。
正确做法是：在递归回溯时统一赋值，即 parent[x] = find(parent[x])，而非先读再写分离操作。这样既保证每次调用都完成压缩，又不改变等价类划分。
- 别用循环 + 单次赋值实现压缩（容易漏节点）
- 避免在
union里手动调用find后再改parent——这会绕过压缩逻辑 - 如果用迭代版
find，需额外缓存路径节点，最后批量更新，否则时间复杂度退化
带按秩合并的 union 操作怎么配对路径压缩
路径压缩和按秩合并（union by rank）可以共存，但要注意：压缩不改变树高，所以 rank 数组仍可安全用于合并决策；但压缩后 rank 不再等于真实高度，仅作上界估计。
实际中建议用 size 合并（union by size）更直观，尤其当需要支持「查询连通分量大小」时。两者性能差异极小，但 size 更易验证、调试。
-
rank初始化全为 0，合并时只在两棵树rank相等时才对新根rank++ - 用
size时，初始化全为 1，合并后新根size += old_root_size - 别在
union里重复调用find两次——应先find(a)和find(b)存到变量，再比较
为什么 find 返回根节点而不是 void
find 必须返回根节点，因为它是所有依赖操作的基础：判断连通性（find(a) == find(b)）、合并（需传入两根）、甚至后续扩展（如维护分量内最小值）。返回 void 或只修改内部状态，会迫使用户额外调用一次 find 获取根，白白多一次几乎完全压缩过的查找。
另外，返回值让接口更函数式，便于链式调用或嵌入表达式，比如 if (dsu.find(x) == dsu.find(y)) { ... } 直观且无副作用。
- 别为了“封装”而隐藏返回值，这不是封装，是掩盖必要信息
- 如果担心频繁调用开销，检查是否误在循环内重复调用——通常只需调用一次并缓存结果
- 返回值类型必须是
int（索引）或size_t，不能是引用或指针，避免悬垂风险
初始化和边界处理最容易漏的三个点
很多线上 bug 出现在初始化阶段：数组越界、未初始化 parent 或 rank/size、节点编号从 1 开始却用 0-based 数组访问。C++ 中这些不会报错，但行为未定义。
典型表现是 find(0) 返回异常大数，或 union(1,2) 后 find(1)==find(2) 为 false——其实只是 parent[1] 是垃圾值。
-
parent数组必须显式初始化为i（即parent[i] = i），不能靠全局变量零初始化 - 若节点编号范围是
[1, n]，数组大小至少为n+1，且初始化从1到n - 构造函数里别用
vector<int>(n)</int>就完事——要加循环赋值，或用vector<int> parent(n+1); iota(parent.begin(), parent.end(), 0);</int>
路径压缩真正起效的前提是：足够多次 find 调用摊平树结构。单次调用看不出区别，但连通性判定密集场景下，不压缩的最坏复杂度是 O(n)，压缩后接近 O(α(n))。不过 α(n) 在工程中基本恒为 4，所以重点其实是别让初始化和合并逻辑把这点优势吃掉。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
