DataStructure/UnionFind.cpp

Back to top page

• category: DataStructure
• View this file on GitHub
  • Last commit date: 2020-04-26 16:04:18+09:00

Description

素集合を管理する。
find(x) : x の属する集合の root を返す。 O(α(N))
unite(u,v) : u,v それぞれが属する集合を併合する。 O(α(N))
size(x) : x の属する集合のサイズを返す。 O(1)
same(u,v) : u,v が同じ集合に属するか判定する。 O(α(N))

Verified with

• Test/UnionFind.test.cpp

Code

//@docs Docs/UnionFind.md
struct UnionFind {
    vector<int> par, sz;
    UnionFind(int n) : par(n), sz(n, 1) {
        iota(par.begin(), par.end(), 0);
    }
    inline int find(int x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return true;
    }
    inline int size(int x) {
        return sz[find(x)];
    }
    inline bool same(int u, int v) {
        return find(u) == find(v);
    }
};

#line 1 "DataStructure/UnionFind.cpp"
//@docs Docs/UnionFind.md
struct UnionFind {
    vector<int> par, sz;
    UnionFind(int n) : par(n), sz(n, 1) {
        iota(par.begin(), par.end(), 0);
    }
    inline int find(int x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return true;
    }
    inline int size(int x) {
        return sz[find(x)];
    }
    inline bool same(int u, int v) {
        return find(u) == find(v);
    }
};

Back to top page