UnionFind
(data_structure/union_find.hpp)

• View this file on GitHub
• Last update: 2024-07-31 03:07:18+09:00
• Include: #include "data_structure/union_find.hpp"

概要

素集合データ構造

集合を扱うためのデータ構造．無向グラフに対して，辺の追加(union)，2頂点が連結かの判定(find)が高速に行える．

コンストラクタ

UnionFind uf(int n)

• $n$ 頂点 $0$ 辺の無向グラフを作る．

制約

• $0 \leq n \leq 10 ^ 8$

計算時間

• $O(n)$

unite

bool uf.unite(int a, int b)

• 無向辺 $(a, b)$ を足す．既に $a, b$ が連結ならfalse，非連結ならtrueを返す．

制約

• $0 \leq a < n$
• $0 \leq b < n$

計算時間

• ならし $O(\alpha(n))$

same

bool uf.same(int a, int b)

• 頂点 $a, b$ が連結かどうか判定する．

制約

• $0 \leq a < n$
• $0 \leq b < n$

計算時間

• ならし $O(\alpha(n))$

root

int uf.root(int a)

• 頂点 $a$ の属する連結成分の代表元を返す．

制約

• $0 \leq a < n$

計算時間

• ならし $O(\alpha(n))$

size

int uf.size(int a)

• 頂点 $a$ の属する連結成分のサイズを返す．

制約

• $0 \leq a < n$

計算時間

• ならし $O(\alpha(n))$

Verified with

• verify/yosupo/yosupo_unionfind.test.cpp

Code

struct UnionFind {
  public:
    UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}

    int root(int a) {
        if(par[a] == -1) return a;
        else return par[a] = root(par[a]);
    }

    bool same(int a, int b) {
        return root(a) == root(b);
    }

    bool unite(int a, int b) {
        int ra = root(a), rb = root(b);
        if(ra == rb) return false;
        if(rank[ra] < rank[rb]) swap(ra, rb);
        par[rb] = ra;
        if(rank[ra] == rank[rb]) rank[ra]++;
        siz[ra] += siz[rb];
        return true;
    }

    int size(int a) {
        return siz[root(a)];
    }

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

#line 1 "data_structure/union_find.hpp"
struct UnionFind {
  public:
    UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}

    int root(int a) {
        if(par[a] == -1) return a;
        else return par[a] = root(par[a]);
    }

    bool same(int a, int b) {
        return root(a) == root(b);
    }

    bool unite(int a, int b) {
        int ra = root(a), rb = root(b);
        if(ra == rb) return false;
        if(rank[ra] < rank[rb]) swap(ra, rb);
        par[rb] = ra;
        if(rank[ra] == rank[rb]) rank[ra]++;
        siz[ra] += siz[rb];
        return true;
    }

    int size(int a) {
        return siz[root(a)];
    }

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

Back to top page