C++如何实现带路径压缩的并查集查找优化-C++-PHP中文网

路径压缩的递归实现更直观，因其天然遵循“先抵达根节点、再回溯统一挂载”的逻辑顺序，避免手动维护路径栈；而循环易漏改中间层节点，导致压缩不彻底。

c++如何实现带路径压缩的并查集查找优化

路径压缩的递归实现为什么比循环更直观

路径压缩的核心目标是让查找过程中经过的所有节点直接指向根节点，从而摊还后续查找的时间复杂度。递归写法天然契合“先找到根，再回溯统一挂载”这一逻辑，避免手动维护栈或指针链。

常见错误是试图在循环中边遍历边修改父指针，却漏掉中间某层节点——比如只改了当前节点的 parent，没处理其原始父节点的父节点，导致压缩不彻底。

递归版本必须保证：递归调用返回的是最终根节点，然后立即将当前节点的 parent 设为该根
不能在递归前就赋值 parent[x] = find(parent[x])，否则会破坏递归链（C++ 中未定义行为风险）
务必启用尾递归优化（编译器通常自动做），否则深度大时可能栈溢出；生产环境建议限制最大集合大小或改用迭代

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 关键：先递归，后赋值
    }
    return parent[x];
}

迭代版路径压缩如何避免两次遍历

迭代写法常被误认为“更安全”，但若实现不当，容易写成两趟扫描：第一趟找根，第二趟从头再走一遍改父指针。这不仅冗余，还多一次缓存不友好的顺序访问。

真正高效的迭代只需一趟：用 vector 记录路径上的所有节点，最后统一设父为根。注意 vector 容量和内存局部性影响——小集合用数组更优，大集合才值得动态分配。

不要用 while (parent[x] != x) { x = parent[x]; } 单独找根，那只是第一趟
记录路径时，推荐 push_back 原始 x，再更新 x = parent[x]，避免漏掉起点
最后遍历时，跳过最后一个（即根节点本身），其余全部设 parent[node] = root

int find(int x) {
    std::vector<int> path;
    while (parent[x] != x) {
        path.push_back(x);
        x = parent[x];
    }
    int root = x;
    for (int node : path) {
        parent[node] = root;
    }
    return root;
}</int>

带路径压缩的 union 操作要注意什么

路径压缩本身不改变 union 的逻辑，但它会让树高趋近于 1，从而削弱按秩合并（union by rank/size）的效果。如果只做路径压缩不做按秩合并，最坏情况仍是 O(n) 单次查找（虽然摊还仍是 O(α(n))）。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

实际项目中，union 函数必须和 find 配套使用，且 rank/size 数组要随压缩动态更新——但注意：路径压缩不改变根的 rank，只改变非根节点的父指针，所以 rank 更新只发生在 union 时。

务必在 union 中先 find(a) 和 find(b)，拿到两个根，再比较 rank 或 size
压缩后的树结构不可预测，不能假设某节点子树大小等于其 size 值（size 只维护根节点的子树规模）
如果用 std::vector<int></int> 存 parent，确保索引合法；用负数表示根+size 时（如 parent[root] = -size），路径压缩后必须保持该约定不变