素集合データ構造（Union-Find木）の実装

クラスカル法など、他ライブラリから呼ばれることがあるので実装を置いておく。

前提

• グループの管理を高速で行うことができるデータ構造
• 実態は木（森）になっている
• ある状態から、グループを併合することができ、分割することはできない
• UnionFind木の機能は基本的に2つである
  • unite（以下の実装ではconnect）：要素(a,b)のグループを併合する
  • is_same：要素(a,b)が同じグループに属しているかを返す
• 計算量改善に2つの工夫がなされている（下に載せたAtCoder社のスライドに図解がある）
  • 経路圧縮：同一グループの頂点を1つの根に直接繋ぐ
  • ランク：併合の際、小さいグループを大きいグループに併合する
• 以上の2点によりunite, isSameは、ならし計算量でO(α(n))となる（α(n)はアッカーマン関数の逆関数でlog_nよりも高速）
• 小さいグループを大きいグループに併合するテクは、マージテクとも呼ばれ、これ単体が解法となる問題もあるほど重要

わかりやすい解説

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

algo-logic.info

• chokudaiさんによる解説放送

検証用問題

onlinejudge.u-aizu.ac.jp

実装

class UnionFind {
private:
  vector<int> parent;

public:
  UnionFind(int n) { parent = vector<int>(n, -1); }

  int root(int a) {
    if (parent[a] < 0)
      return a;
    return parent[a] = root(parent[a]);
  }

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

  bool connect(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) {
      return false;
    }
    if (size(a) < size(b))
      swap(a, b);
    parent[a] += parent[b];
    parent[b] = a;
    return true;
  }

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