路径压缩需递归实现并确保每层返回前更新父节点，或迭代时缓存路径统一修改；与按秩合并共存时rank仅用于union决策，不反映压缩后高度。
为什么路径压缩不能只靠一次 find 就完事
路径压缩的核心目标是让后续 find 操作接近 O(1)，但很多人误以为只要在 find 里写一句 parent[x] = find(parent[x]) 就万事大吉。问题在于：如果递归返回时没正确更新当前节点的父节点，或者用了非递归写法却忘了回溯修改，压缩就失效了。更隐蔽的是，和按秩合并（unionByRank）混用时，若先做了路径压缩再调用 union，可能破坏秩信息——因为压缩会改变树高，但 rank 数组并未同步更新。
实操建议：
- 必须用递归版
find实现压缩，确保每层返回前都重置parent[x] - 若坚持迭代写法，需额外缓存访问路径（如用
std::vector存下从 x 到根的所有节点），再统一指向根 - 按秩合并与路径压缩可共存，但
rank仅用于 union 决策，不反映压缩后的实际高度，因此无需、也不应被路径压缩修改
带路径压缩的 find 函数怎么写才不出错
最简且健壮的递归实现是：int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }。注意三点：一是必须用赋值表达式 parent[x] = find(...)，而非先调用再赋值；二是不能写成 return parent[x] = parent[x] == x ? x : find(parent[x]);，这会因运算符优先级导致逻辑错误；三是若用 std::vector<int></int> 存 parent，务必保证索引合法（常见坑：用负数或越界下标调用 find）。
示例中易错写法对比：
立即学习“C++免费学习笔记（深入）”；
int find_bad(int x) {
if (parent[x] != x) {
int root = find_bad(parent[x]);
parent[x] = root; // ✅ 正确，显式赋值
return root;
}
return x;
}
int find_broken(int x) {
if (parent[x] != x) {
return parent[x] = find_broken(parent[x]); // ✅ 等价于上面，简洁
}
return x;
}
// ❌ 错误：下面这行会先算 parent[x] == x ? x : ...，再把结果赋给 parent[x]
// return parent[x] = (parent[x] == x ? x : find_broken(parent[x]));
初始化、union 和 find 的配合要点
并查集不是三个独立函数，而是一套状态协同机制。初始化时，parent[i] = i 是必须的，但常被忽略的是：若集合元素编号不连续（比如只用 1,3,5,7），就不能简单用 vector 下标遍历，得维护一个活跃节点集合或用 std::map。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
实操建议：
-
unionSets(int a, int b)必须先find(a)和find(b)，再比较根是否相同——否则会把同一集合内节点重复 union，浪费且可能干扰 rank - 路径压缩只发生在
find中，union过程中绝不直接修改parent（除最终的根指向外），否则压缩失效 - 若需频繁查询连通性（如判断两点是否同属一集合），直接用
find(a) == find(b)，别缓存中间结果，因为路径压缩会让后续find更快
性能陷阱：看似优化实则拖慢的常见操作
路径压缩本意是降均摊复杂度，但有些“优化”反而引入开销。比如在 find 中加日志打印、或每次调用都检查 parent[x] （误当并查集支持负数标记）；又比如用 <code>std::shared_ptr 管理 parent 数组——指针解引用+引用计数远超数组随机访问。
另一个典型问题是过早优化：在小规模数据（n find 耗时差不到 10ns，而 n=1e6 时差距可达百倍。
真正该关注的点：
- 确保
parent数组用std::vector<int></int>连续存储，避免std::list或哈希表 - 禁用调试宏（如
_GLIBCXX_DEBUG）编译，否则vector的边界检查会吃掉大部分性能 - 若需支持删除操作，标准路径压缩并查集不适用——得换动态图算法，别硬改
parent数组
路径压缩的收益高度依赖使用模式：大量查询 + 少量合并时效果显著；反之，如果每 union 之后立刻 find 全部节点，压缩带来的缓存局部性优势会被反复刷掉。
