structure/union-find.cpp

Back to top page

• category: structure
• View this file on GitHub
  • Last commit date: 2020-06-15 15:20:08+09:00

Verified with

• test/union-find.test.cpp

Code

class UnionFind {
public:
    UnionFind(const int n) : par(n), rank(n, 0), sz(n, 1) {
        rep(i, n) par[i] = i;
    }

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

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;

        if (rank[x] < rank[y]) {
            par[x] = y;
            sz[y] += sz[x];
        } else {
            par[y] = x;
            sz[x] += sz[y];
            if (rank[x] == rank[y]) {
                ++rank[x];
            }
        }
    }

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

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

private:
    vector<int> par, rank, sz;
};

#line 1 "structure/union-find.cpp"
class UnionFind {
public:
    UnionFind(const int n) : par(n), rank(n, 0), sz(n, 1) {
        rep(i, n) par[i] = i;
    }

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

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;

        if (rank[x] < rank[y]) {
            par[x] = y;
            sz[y] += sz[x];
        } else {
            par[y] = x;
            sz[x] += sz[y];
            if (rank[x] == rank[y]) {
                ++rank[x];
            }
        }
    }

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

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

private:
    vector<int> par, rank, sz;
};

Back to top page