Union Find 木の実装

最近 AtCoder の過去問を解いていて、Union Find 木を使うと解くことができる問題に出会いました。これまで 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);
  }
};