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

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

路径压缩必须在find中实现，因其本质是将查找路径上所有节点直接指向根以摊平树高；若放在union或初始化中则无法暴露待压路径，单步压缩无效，而递归或迭代全路径压缩可使后续查询趋近o(1)。

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

路径压缩为什么必须在 find 里做

路径压缩的本质是让查找过程中经过的所有节点直接指向根节点，从而摊平树高。它不能放在 union 或初始化里，因为只有 find 调用时才暴露出需要压缩的路径。常见错误是只改了当前节点的父指针（比如写成 parent[x] = parent[parent[x]]），这叫“单步压缩”，效果远不如递归/迭代式全路径压缩。

正确做法是在 find 返回前统一重定向：所有被访问过的节点都设为根节点的直接子节点。这样后续查询该路径上任意节点，复杂度立刻降到接近 O(1)。

递归写法最简洁但要注意栈深度

递归实现路径压缩逻辑清晰，一行核心代码就能完成：先递归找到根，再把当前节点父指针设为根。但 C++ 默认栈空间有限，如果并查集规模超 10⁵ 且树退化成链，可能触发栈溢出。

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 关键：先更新再返回
    }
    return parent[x];
}

必须是 parent[x] = find(parent[x])，不是 return find(parent[x])，否则没做压缩
数组 parent 需初始化为 parent[i] = i
若数据规模大（如 ≥ 2×10⁵），建议改用迭代版本

迭代写法更安全，但需两次遍历

迭代版避免栈溢出，代价是多一次遍历：第一次找根，第二次回溯改父指针。注意不能边找边改——那样会破坏路径，导致找不到真正的根。

int find(int x) {
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 第二次遍历：从 x 到 root，全部挂到 root 下
    while (x != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}