UnionFind
(datastructure/unionfind/unionfind.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "datastructure/unionfind/unionfind.hpp"

概要

連結成分を管理するデータ構造. 素集合データ構造.

計算量

$O(\alpha (n))$

使用例

• UnionFind uf(V) : $V$頂点のUnionFindを定義.
• uf.unite(x, y) : $x$と$y$を連結にする.
• uf.same(x, y) : $x$と$y$が連結かを返す.
• uf.size(x) : $x$の属する連結成分の大きさを返す.
• uf.size() : 連結成分の個数を返す.

Verified with

• test/aoj/GRL_2_A.test.cpp
• test/yosupo/unionfind.unionfind.test.cpp

Code

/**
* @brief UnionFind
* @docs docs/datastructure/unionfind/unionfind.md
*/

struct UnionFind {
    int sz;
    vector<int> parent;
    UnionFind(int sz)
        : sz(sz), parent(sz, -1) {}
    bool unite(int x, int y) {
        if ((x = find(x)) != (y = find(y))) {
            if (parent[y] < parent[x]) swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            --sz;
            return true;
        }
        return false;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
    int size(int x) { return -parent[find(x)]; }
    int size() { return sz; }
};

#line 1 "datastructure/unionfind/unionfind.hpp"
/**
* @brief UnionFind
* @docs docs/datastructure/unionfind/unionfind.md
*/

struct UnionFind {
    int sz;
    vector<int> parent;
    UnionFind(int sz)
        : sz(sz), parent(sz, -1) {}
    bool unite(int x, int y) {
        if ((x = find(x)) != (y = find(y))) {
            if (parent[y] < parent[x]) swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            --sz;
            return true;
        }
        return false;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
    int size(int x) { return -parent[find(x)]; }
    int size() { return sz; }
};

Back to top page