ei1333's page

素集合データ構造(Union-Find)

説明

集合を高速に扱うためのデータ構造。集合を合併する操作(unite), ある要素がどの集合に属しているか(find)を問い合わせる操作を行うことが出来る。

使い方

• $unite(x,y)$: 集合 $x$ と $y$ を併合する. 併合済のとき $false$, 未併合のとき $true$ が返される
• $find\left(k\right)$: 要素 $k$ が属する集合を求める
• $size\left(k\right)$: 要素 $k$ が属する集合の要素の数を求める

計算量

$O\left(\alpha \right(n\left)\right)$

$\alpha$ はアッカーマンの逆関数

実装例

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return(false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return(true);
  }

  int find(int k)
  {
    if(data[k] < 0) return(k);
    return(data[k] = find(data[k]));
  }

  int size(int k)
  {
    return(-data[find(k)]);
  }
};

応用 1: 2部グラフの頂点彩色

Union-Find を用いると $2$ 部グラフ判定とその副作用として彩色が可能。頂点を倍長して偶奇に分ける。隣接頂点を同じ色にするときは, $unite(u,v)$ と $unite(u+N,v+N)$, 異なる色にするときは $unite(u+N,v)$ と $unite(u,v+N)$ をする。

struct Bipartite_Graph : UnionFind
{
  vector< int > color;

  Bipartite_Graph(int v) : color(v + v, -1), UnionFind(v + v) {}

  bool bipartite_graph_coloring()
  {
    for(int i = 0; i < color.size() / 2; i++) {
      int a = find(i);
      int b = find(i + (int) color.size() / 2);
      if(a == b) return (false);
      if(color[a] < 0) color[a] = 0, color[b] = 1;
    }
    return (true);
  }

  bool operator[](int k)
  {
    return (bool(color[find(k)]));
  }
};

応用 2: データ構造をマージする一般的なテク

データ構造をマージする一般的なテク(Weighted-Union-Heuristic) は, Union-Find の unite 操作で常に大きい木の根が全体の根になるよう連結する(union-by-rank) の考え方と同様。

補足: 経路圧縮, ランクによる統合の計算量

経路圧縮, ランクによる統合の $2$ つの工夫をすると計算量は $1$ クエリあたり $O\left(\alpha \right(n\left)\right)$ となるが, 経路圧縮あるいはランクによる統合片方だけ行うと $O\left(\log n\right)$ となる。[証明: アルゴリズムとデータ構造 p268-270]

応用 3: UnionFindに何かをもたせるやつ

左端と右端をもたせたUnionFind の実装例を以下にあげる。

struct UnionFindRange
{
  vector< int > data;
  vector< int > left, right;

  UnionFindRange(int sz)
  {
    data.assign(sz, -1);
    left.resize(sz);
    right.resize(sz);
    for(int i = 0; i < sz; i++) left[i] = i;
    for(int i = 0; i < sz; i++) right[i] = i;
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    left[x] = min(left[x], left[y]);
    right[x] = max(right[x], right[y]);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  pair< int, int > range(int k)
  {
    k = find(k);
    return {left[k], right[k]};
  };

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

応用 4: 部分永続UnionFind

$t$ 番目のクエリを処理した時点における頂点 $x$ が含まれる連結成分の根や大きさを求めるクエリを $O\left(\log n\right)$ で行うことができる。

struct PartiallyPersistentUnionFind
{
  vector< int > data;
  vector< int > last;
  vector< vector< pair< int, int > > > add;
 
  PartiallyPersistentUnionFind() {}
 
  PartiallyPersistentUnionFind(int sz) : data(sz, -1), last(sz, 1e9), add(sz)
  {
    for(auto &vs : add) vs.emplace_back(-1, -1);
  }
 
  bool unite(int t, int x, int y)
  {
    x = find(t, x);
    y = find(t, y);
    if(x == y) return false;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    add[x].emplace_back(t, data[x]);
    data[y] = x;
    last[y] = t;
    return true;
  }
 
  int find(int t, int x)
  {
    if(t < last[x]) return x;
    return find(t, data[x]);
  }
 
  int size(int t, int x)
  {
    x = find(t, x);
    return -prev(lower_bound(begin(add[x]), end(add[x]), make_pair(t, 0)))->second;
  }
};

応用 5: 完全永続UnionFind

永続配列を使うとできる。

struct PersistentUnionFind
{
  PersistentArray< int, 3 > data;

  PersistentUnionFind() {}

  PersistentUnionFind(int sz)
  {
    data.build(vector< int >(sz, -1));
  }

  int find(int k)
  {
    int p = data.get(k);
    return p >= 0 ? find(p) : k;
  }

  int size(int k)
  {
    return (-data.get(find(k)));
  }

  PersistentUnionFind unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return *this;
    auto u = data.get(x);
    auto v = data.get(y);

    if(u < v) {
      auto a = data.mutable_get(x);
      *a += v;
      auto b = data.mutable_get(y);
      *b = x;
    } else {
      auto a = data.mutable_get(y);
      *a += u;
      auto b = data.mutable_get(x);
      *b = y;
    }
    return *this;
  }
};

問題例

• 検証済ATC 001_B Union Find
• AOJ DSL_1_A 互いに素な集合
• 検証済(応用1)CF #383 C. Arpa’s overnight party and Mehrdad’s silent entering(Submittion: #24955808)
• 検証済(応用1)CF #400 D. The Door Problem(Submittion: #24955583)
• 検証済(応用4)AGC 002_D Stamp Rally

参考資料

• 素集合データ構造 - Wikipedia
• Union find(素集合データ構造) - AtCoder
• プログラミングコンテストでのデータ構造 - iwi
• やぶについて書きます