pyhaya’s diary

プログラミング、特にPythonについての記事を書きます。Djangoや機械学習などホットな話題をわかりやすく説明していきたいと思います。

Union Find 木の実装

最近 AtCoder の過去問を解いていて、Union Find 木を使うと解くことができる問題に出会いました。これまで Union Find 木は使ったことがなく、聞いたことがあるくらいだったのでこの問題を解くために勉強しました。この記事では Union Find 木がどのようなデータ構造で、どんなことに使えるのかを説明したいと思います。

Union Find 木はどんなデータ構造か

名前にあるように、 Union Find 木は木構造です。つまり、親要素があって、それに連なる子要素がいくつかあるような構造をしています。木構造として有名なものに二分木やそれの特殊なものとしての二分探索木などがありますが、これらに対して Union Find 木は複数の木構造の集合からなるという特徴があります。

同じ木に属している要素は「同じグループ」に属していると解釈されます。つまり Union Find 木は特定の要素が他の要素と同じグループに属しているかどうかを判定するのに適しています

Union Find 木の実装

Union Find 木を C++ で実装してみます。

struct UnionFind {
  vector<int> par;
 
  UnionFind(int N) : par(N) {
    for (int i = 0; i < N; i++) par[i] = i;
  }
 
  int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
 
  void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
 
    if (rx == ry) return;
    par[rx] = ry;
  }
 
  bool same(int x, int y) {
    return root(x) == root(y);
  }
};

UnionFind という名前の構造体を定義します。この構造体は par という要素をもっており、par はそれぞれの要素の親要素をもっています。

初期化

簡単のために考える要素は0 ~ N-1 までの連続する整数であるとして話を進めます。最初に、Union Find 木を初期化するときには全ての要素の親要素が自分自身 (par[i] = i) になるように初期化します。

一番上の親要素の取得

特定の要素の属する木の最も上にいる親要素を取得するメソッドを定義します。par[x] で x と直接つながっている親を取得できるので、これを再帰的にたどっていけば一番上の親に到達できます。

要素の結合

要素 x と要素 y が同じグループに属するとして結合します。x 属する木に y を結合するとして話を進めていきます。これは非常に簡単で、 y の親を x の親にすればよいです。

2つの要素が同じグループに属するか判定

2つの要素の一番上の親が同じかどうかを判定すればいいだけです。