素集合データ構造 (Union-Find data structure, Disjoint-set data structure)

概要

Union-Findでは以下の操作を行うことができる

  • \(union(u, v)\) : 要素uの属するグループと要素vが属するグループを１つにまとめる

  • \(find(u)\) : 要素uが属するグループを求める

\(find(u) = find(v)\) であればuとvは同じグループに属することが分かる

計算量

\(O(\alpha(n))\)

(ただし、 \(\alpha\) はアッカーマン関数の逆関数)

実装 (Linking by index)

#define N 100008

int parent[N];
int root(int x) {
  if(x == parent[x]) {
    return x;
  }
  return parent[x] = root(parent[x]);
}

bool unite(int x, int y) {
  int px = root(x), py = root(y);
  if(px == py) return false;

  if(px < py) {
    parent[py] = px;
  } else {
    parent[px] = py;
  }
  return true;
}

// 以下で初期化
//
// rep(i, n) parent[i] = i;
//

戻る