并查集模板

技术文章 10个月前 完美者
1,989 0

标签:ret   ted   connect   --   ==   cte   false   路径压缩   iot   

// 并查集模板,包含路径压缩(参考 findset 函数)以及按秩合并(参考 sz 变量)
class UF {
public:
    vector<int> fa;
    vector<int> sz;
    int n;
    int comp_cnt;
    
public:
    UF(int _n): n(_n), comp_cnt(_n), fa(_n), sz(_n, 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    
    int findset(int x) {
        return fa[x] == x ? x : fa[x] = findset(fa[x]);
    }
    
    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (sz[x] < sz[y]) {
            swap(x, y);
        }
        fa[y] = x;
        sz[x] += sz[y];
        --comp_cnt;
        return true;
    }
    
    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

并查集模板

标签:ret   ted   connect   --   ==   cte   false   路径压缩   iot   

原文地址:https://www.cnblogs.com/bgyx-hyyy/p/14163893.html

版权声明:完美者 发表于 2020-12-25 12:01:55。
转载请注明:并查集模板 | 完美导航

暂无评论

暂无评论...