データ構造の一つであるDisjoint Setsと、それを管理するUnion-Findアルゴリズムについて勉強した内容のまとめです。

この記事の内容

Disjoint Sets とは何か
Disjoint Sets の実装のアイディア
例題を解く

Disjoint Sets とは？

複数の集合を考えたとき、それらの要素の重複がない（どの２つをとっても、共通部分が空集合）とき、これらの集合は「互いの素である」と言います。このような互いに素な集合たちを管理するデータ構造にDisjoint Setsがあります。そのまんまのネーミング。

Disjoint Setsに対する操作は次。

makeSet(x)： xをただ１つの要素とする集合を作る
find(x)：xが属する集合の代表の要素を見つける
unite(x, y)：xが属する集合とyが属する集合の和集合を取る

Union-Findアルゴリズム

Disjoint Setsに対して、「ある２つの要素が同じ集合に属するか」を調べるアルゴリズムをUnion Findと呼びます。上の操作を組み合わせて実装できます。

実装のアイディア

具体的なDisjoint Setsの構造と実装の考え方を見てみます。まず、各集合は木構造として実装されます。一般に木の集合を森いい、木として実装された互いに素な集合をまとめたものをDisjoint Sets Forestと呼びます。つまり、Disjoint Setsは森（Disjoint Sets Forest）として実装されます。

find

各集合を区別するために、それぞれの木の根を代表とします。そして、それぞれの要素から根まで到達できるように、各ノードがそれぞれの親へのポインタを持ちます。

f:id:programgenjin:20190324193323p:plain

ところが、この方法だと、一つ一つ根まで親をたどって行かなければならず、計算量が多くなります。直接ポインタを根に繋げてしまえば少ない計算ですみます。そこで、ある要素から根までたどっていくとき、途中にあるノードのポインタが根をさすようにつなぎ変えることを考えます。これを経路圧縮と言います。

f:id:programgenjin:20190324194354p:plain

例えば、これを、次のように経路圧縮します。

f:id:programgenjin:20190324194459p:plain

unite

２つの集合を合併するには、木をくっつけるだけでOKです。具体的には、２つの木のどちらか一方の根を選んで、新しい集合の代表とし、他方の根のポインタを新しい代表へのポインタとします。このとき、計算量を考えて、合併後の木の高さがなるべく小さくなるように、低い木を高い木にくっつけるようにします。

f:id:programgenjin:20190324200749p:plain

例えば、上の木に対して unite(2, 4) を施すと、

f:id:programgenjin:20190324200904p:plain

要素xを表すノードの高さをrank[x]とし、木の高さを管理します。初期値は全てのxについてrank[x] = 0、同じ高さの木を合併するときに新しく代表となったノードの高さを１増やせば良いでしょう。

問題を解いてみる

次の問題を解きます。

互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge

解答例：

#include<iostream>
using namespace std;

const int N = 10000;

class DisjointSet {
  int parent[N], rank[N];

public:
  // コンストラクタ
  DisjointSet(int n) {
    for (int i = 0; i < n; i++) make_set(i);
  };
  
  void make_set(int x) {
    rank[x] = 0;
    parent[x] = x;
  }
  
  int find(int x) {
    if (x != parent[x]) parent[x] = find(parent[x]);
    return parent[x];
  }
  
  void unite(int x, int y) {
    int root_x, root_y;
    root_x = find(x);
    root_y = find(y);
    
    if (rank[root_x] > rank[root_y]) {
      parent[root_y] = root_x;
    } else if (rank[root_x] < rank[root_y]) {
      parent[root_x] = root_y;
    } else {
      parent[root_y] = root_x;
      root_x++;
    }
  }  

  bool same(int x, int y) {
    return find(x) == find(y);
  }
};



int main() {
  int i, n, q, com, x, y;

  cin >> n >> q;

  DisjointSet ds(n);  // 初期化

  for (i = 0; i < q; i++) {
    cin >> com >> x >> y;
    // same
    if (com) cout << ds.same(x, y) << endl;
    // unite
    else ds.unite(x, y);
  }  

  return 0;
}

メンバ関数findを再帰関数を用いて実装していることに注意。根の親が根なので、根まで行き着くと次々と根となっている要素が返され、経路上にある全てのノードの親が根となることがわかります。

まとめ

Disjoint Setsの考え方を勉強しました。問題を解くことを通してUnion Findの実装を行いました。

参考

渡部有隆（2015）「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 Ozy・秋葉拓哉協力株式会社マイナビ

プログラミング原人の進化論

オレ　プログラミング　ベンキョウ　スル。マナンダ　コト　カク。

Disjoint SetsとUnion Find