c++如何实现并查集算法_c++ 路径压缩与按秩合并优化【案例】_技术教程

并查集基础结构用数组模拟父节点最稳妥，parent[i]初始化为i；find需路径压缩且避免递归栈溢出；按秩合并的秩是树高上界估计值，非真实高度；完整模板应封装parent、rank并配套使用两种优化。

并查集基础结构怎么写才不容易出错

直接用数组模拟父节点关系最稳妥，parent[i] 表示节点 i 的父节点，初始化时设为自身。别用指针或动态对象——C++ 里下标访问快、内存连续、无构造析构干扰。

常见错误是把 find 写成递归但没处理栈溢出（尤其数据量大时），或者忘了在查找后更新父节点（路径压缩失效）。

parent 数组大小必须 ≥ 最大可能节点编号（推荐从 0 或 1 开始统一编号）
初始化必须显式循环赋值：parent[i] = i，不能靠全局变量默认零初始化（除非你确定节点编号从 0 开始且全用上）
合并操作前先 find 两次，比较根而非原编号

路径压缩为什么必须写在 find 里而不是 union 里

路径压缩本质是“懒更新”：只在查询根时顺手压平路径。如果只在 union 里做，那中间多次 find 仍走长链，时间复杂度退化到 O(n)。

正确做法是在 find 返回前，把当前节点的父节点直接设为根——注意不是返回根，而是改 parent[i]，再返回。

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 递归压缩：先压子树，再设自己父为根
    }
    return parent[x];
}

非递归写法更省内存（防爆栈），但要多一次遍历找根再二次遍历改父：

int find(int x) {
    int root = x;
    while (parent[root] != root) root = parent[root];
    while (x != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

按秩合并的“秩”到底该存什么

这里的“秩”不是真实树高，而是**上界估计值**，仅用于决定合并方向。用 rank[i] 表示以 i 为根的树的近似深度，初始全为 0。合并时，总把秩小的树挂到秩大的根下；相等时任选其一，被挂方秩 +1。

关键点：秩只增不减，且永远 ≤ 实际树高；它和路径压缩可共存，但压缩后秩不再反映真实结构——这没关系，因为秩只服务合并决策。

别把 rank 和节点数量（size）混用：按大小合并（union-by-size）是另一种优化，效果接近但语义不同
如果同时用路径压缩 + 按秩合并，均摊时间复杂度是 O(α(n))，α 是反阿克曼函数，实际中 ≤ 4
调试时可打印 rank[root] 观察是否合理增长，但别拿它当树高用

完整带优化的并查集模板怎么组织

把 parent 和 rank 封装进 class，避免裸数组越界或生命周期错乱。构造函数接收节点数，强制初始化；提供 unite（非对称命名比 merge 更准）、same、size（需额外维护 sz[]）等接口。

容易忽略的是：按秩合并与路径压缩必须配套使用才能达到最优；单独用路径压缩已够快，但加秩合并能进一步减少树高波动。

class UnionFind {
    vector parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) ++rank[x];
    }
    bool same(int x, int y) { return find(x) == find(y); }
};