Skip to content →

Union Find

「集合の合体(union)」と「要素の属す集合の発見(find)」を効率的に行うデータ構造 Union Find の解説をします。

処理したいクエリを正確に述べると次のようになります。

要素が相異なる一元集合が \(n\) 個あります。次の2種類のクエリが何度も与えられるので、処理してください(\(a, b\) はクエリごとにバラバラ)。

  • find(a) : 要素 \(a\) の属す集合(の代表元)を見つけてください。
  • union(a, b) : 要素 \(a, b\) の属す集合を合体して、一つの集合にしてください。

\(a, b\) が同じ集合に属すか? というクエリも find(a) == find(b) によって処理できます。

計算量はアッカーマン関数 \(A(n,n)\) の逆関数 \(\alpha\) を用いてならし \(O(\alpha(n))\) 、最悪 \(O(\log(n))\) となります。

アルゴリズム

各要素を一つの頂点、各集合を一つの木に対応させます。また、木の根をその集合の代表元として扱います。

union(a, b) は a, b の属す二つの木を一つの木に合体させればよいです。一方の木の根を、もう一方の木の根の子とします。

find(a) は a の属す木の根(集合の代表元)を見つければよいです。a から親を辿れば height(a) ステップで根が見つかります。

union(a, b) は二つの木の根を繋ぐので、find(a) と find(b) を内包しています(根が見つかれば、繋ぐこと自体は \(O(1)\) )。find は木の高さだけ計算量が必要でした。そこで、木の高さをできるだけ小さくすると find, union の計算量が小さくなります。木の高さを小さくするための工夫として、次に述べる Union by Size/Rank と Path Compression/Halving/Splitting があります。

Union By Size/Rank

木の頂点数が小さい方を子として、もう一方の木の根につなぐのが Union by Size です。また、木の高さが低い方を子として、もう一方の木の根につなぐのが Union by Rank です。

両方とも、単体では実時間 \(O(\log(n))\) / クエリ になります。これは、Union by Size/Rank では、親を辿るたびに部分木の大きさが二倍以上になり、木の高さが \(\log_2(n)\) で抑えられるからです。Union by Rank の場合、高さ \(k\) の木は高さ \(k-1\) の2つの木を Union したときにできます。従って帰納法により、親を辿るたびに部分木のサイズが二倍になることが言えます。Union by Size は構成法から明らかです。詳しい証明はUnion Find の計算量をご参照ください。

Path Compression/Halving/Splitting

find(x) としたとき、x から根までのパス上の頂点全てを、根に直接つなぐのが path compression です。C++のコードは次の通り。

int find(int x) {
    if (parent[x] == x) return x;
    else {
        parent[x] = find(parent[x]);
        return parent[x];
    }
}

find(x) としたとき、x と根を繋ぐパス上の頂点のうち高さ偶数のものを、祖父(親の親)につなぐのが path halving です。根の親は自分自身であるとすると実装が簡素になります。非再帰で書きやすいという特徴があります。C++のコードは次の通り。

int find(int x) {
    if (parent[x] == x) return x;
    else {
        parent[x] = parent[parent[x]];
        return find(parent[parent[x]]);
    }
}

find(x) としたとき、x と根を繋ぐパス上の頂点を祖父(親の親)につなぐのが path splitting です。根の親は自分自身であるとすると実装が簡素になります。path halving と同じく、非再帰で書きやすいという特徴があります。C++のコードは次の通り。

int find(int x) {
    if (parent[x] == x) return x;
    else {
        int next = parent[x];
        parent[x] = parent[parent[x]];
        return find(next);
    }
}

union by size/rank と path-compression/halving/splitting を組み合わせると、計算量が iterated logarithm \(O(\log^*(n))\) で抑えられることは Union Find の計算量 をご覧ください(より強く、アッカーマン関数の逆関数で抑えられることが言えますが、本サイトでは証明をしていません)。

実装

union by size と path-splitting で実装した C++ のコードは次の通りです。union は予約語だったので merge にしています。


#include "vector"

using namespace std;

struct UnionFind {
  vector<int> parent;
  vector<int> size;
  
  UnionFind(int n) {
    parent.resize(n);
    size.resize(n);
    for (int i = 0; i < n; ++i) parent[i] = i;
  }
  
  int find(int x) {
      if (parent[x] == x) return x;
      else {
          parent[x] = parent[parent[x]];
          return find(parent[parent[x]]);
      }
   }
  
  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    size[x] += size[y];
    parent[y] = x;
  }
  
  bool equiv(int x, int y) {
    return find(x) == find(y);
  }
};

関連記事

Union Find の計算量
最悪計算量を最小化した Union Find
部分永続 Union Find

一番好きなデータ構造かも。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA