Union-Find
(DataStructure/UnionFind.cpp)

• View this file on GitHub
• Last update: 2021-06-16 19:56:29+09:00

説明

別名 Disjoint Set Union 。2つの要素が含まれている集合の併合や、2つの要素が同じ集合に含まれているかの判定などが高速に出来る。実装には根つき木を利用している。

• UnionFind uf(int n) : それぞれの要素数が 1 である n 個の集合を生成する。
• int uf.find(int x) : xが属する集合を表す根つき木の頂点を返す。計算量 $O(\alpha(n))$
• void unite(int x,int y) : xが属する集合とyが属する集合を併合する。計算量 $O(\alpha(n))$
• bool same(int x,int y) : xとyが同じ集合に属しているかを判定する。計算量 $O(\alpha(n))$
• int size(int x) : xが属している集合の要素数を返す。計算量 $O(\alpha(n))$

※ $\alpha(n)$ はアッカーマン関数の逆関数を表す。実用上は定数と見なせる。

Required by

• Graph/Kruskal.cpp

Verified with

• Test/AOJ/Kruskal.test.cpp
• Test/yosupo-judge/UnionFind.test.cpp

Code

class UnionFind {
    vector<int> par;
    vector<int> siz;

public:

    UnionFind(int n) {
        par.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++) {
            par[i] = i;
            siz[i] = 1;
        }
    }

    int find(int x) {
        if(par[x] == x) {
            return x;
        }
        else {
            return par[x] = find(par[x]);
        }
    }

    void unite(int x,int y) {
        x = find(x);
        y = find(y);
        if(x == y) {
            return;
        }
        if(siz[x] < siz[y]) {
            swap(x,y);
        }
        par[y] = x;
        siz[x] += siz[y];
    }

    bool same(int x,int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }
};

#line 1 "DataStructure/UnionFind.cpp"
class UnionFind {
    vector<int> par;
    vector<int> siz;

public:

    UnionFind(int n) {
        par.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++) {
            par[i] = i;
            siz[i] = 1;
        }
    }

    int find(int x) {
        if(par[x] == x) {
            return x;
        }
        else {
            return par[x] = find(par[x]);
        }
    }

    void unite(int x,int y) {
        x = find(x);
        y = find(y);
        if(x == y) {
            return;
        }
        if(siz[x] < siz[y]) {
            swap(x,y);
        }
        par[y] = x;
        siz[x] += siz[y];
    }

    bool same(int x,int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }
};

Back to top page