路径压缩必须在find里做，因为只有遍历查找路径时才能获取中间节点及其父节点信息并统一指向根；union中无路径遍历，无法执行压缩。
路径压缩为什么必须在 find 里做，而不是 union 里
路径压缩的本质是让查找路径上的所有节点直接指向根节点，从而摊平树高。这个操作只能发生在 find 过程中——因为只有遍历到某个节点时，你才清楚它的父节点是谁、它最终要连向哪个根。如果在 union 里试图“顺便压缩”，既没遍历路径，也没拿到中间节点的引用，根本无从下手。
常见错误是写成这样：
void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
parent[rx] = ry;
// 错误：这里以为能“顺手压缩 ry 的子树”，其实没遍历，压不了
}
正确做法是：每次调用 find 都递归（或迭代）回溯，把沿途每个节点的 parent 改成根。
递归版路径压缩怎么写才安全
递归实现最简洁，但要注意两点：栈深度风险和赋值顺序。C++ 默认栈空间有限，节点数超 10⁵ 时可能爆栈；另外必须先拿到根，再统一更新父指针，否则会“找错根”。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 正确写法：
return parent[x] = find(parent[x])—— 先算出find(parent[x])得到根，再把parent[x]设为该根，最后返回 - 错误写法：
return find(parent[x]) = parent[x]—— 赋值方向反了，语法也不合法 - 如果担心栈溢出，改用迭代版：先循环找到根，再走一遍路径把每个节点
parent设为根
路径压缩 + 按秩合并要不要一起用
要。路径压缩单独用能让单次 find 接近 O(α(n))，但反复 union 可能导致树退化成链；按秩合并（union by rank/size）则从结构上限制树高增长。两者叠加才是理论最优解。
注意点：
-
rank数组只在union时更新，且仅当两棵树秩相等时才给新根加 1；路径压缩不改变rank值 - 用
size替代rank更直观（合并时小树挂大树下），但复杂度一样，选一个保持逻辑清晰就行 - 别把路径压缩和按秩合并混在同一个函数里“优化”——
find只管压缩，union只管比较和挂接
为什么 find 返回根后还要 parent[x] = root
因为路径压缩不是“查完就完”，而是“查的同时改”。如果只返回根却不改 parent[x]，下次查 x 还得走老路。关键就在这一句：parent[x] = find(parent[x]) 中的赋值动作。
容易忽略的细节：
- 数组索引必须合法——
x得在[0, n)范围内，否则parent[x]访问越界 - 初始化时每个
parent[i] = i，否则find一进递归就跳飞 - 如果用了 vector
parent，确保 size >= n，且没用 push_back 动态扩容破坏索引连续性
路径压缩真正起效的地方，永远在 find 函数体内部那行赋值里；漏掉它，前面所有设计都白搭。
