Union-Find の実装方法まとめ

本記事は、Union-Find に関して筆者がこれまでに得た知識や実装経験からその全体像をまとめたものであり、詳細は省略されています。図解もありません。
したがって、既に Union-Find の実装経験がある人や、いくつか記事を読んで知識を持っている人を主な対象としています。

もしまだ Union-Find についてまったく知らないという場合、まず次に挙げるような資料に目を通すことをおすすめします。

• AtCoder Typical Contest 001 B - Union Find の下部にある解説資料
• Union-Find木 (いかたこのたこつぼ)
• 素集合データ構造 (Wikipedia)

Union-Find の仕様

Union-Find は、集合の統合 (グラフでいうと連結) に関するアルゴリズムで、素集合データ構造 (disjoint-set data structure) とも呼ばれます。
Union-Find の持つ機能は、次のように定義されます。ここで x, y は、いずれかの集合に含まれる要素を表す ID であるとします。

• Union(x, y)：x を含む集合と y を含む集合を統合する (連結する)
  • 戻り値は、既に同一の集合であった場合は false、新たに統合した場合は true とする。戻り値は必須ではない。
• Find(x)：x を含む集合を一意に表すことのできる値やインスタンスを返す
  • 具体的に何を返すかは実装に依存する。例えば「集合を代表するような特別な要素」「集合そのものを表すインスタンス」など。

また Find ができれば、その戻り値を比較することにより、次の判定もできます。

• Same(x, y)：x と y が同じ集合に含まれているかどうかを判定する (true/false を返す)

文献によっては、Find の代わりに Same が定義されていることがあります。

注意
上記では、抽象データ型としての外部仕様を示しているにすぎません。例えば「木構造かどうか」ということすらこの時点では決まっていません。

Union-Find の実装方法

前提

• 要素の個数を $n$ とし、配列の長さとして使えるほどには小さいとする
• 各要素を表す ID は $0, 1, 2, \cdots , n-1$ とする (配列が 0-based の場合)

以下に示すように、リストによる実装と木構造による実装があります。

(1) リストによる実装

各リストが集合を表し、要素そのものを保持する単純な実装です。
木構造ではなく、アルゴリズム初心者でも十分に思いつく可能性があります。ここでいうリストは、配列リストでも連結リストでもかまいません。

まず、工夫を入れる前の基本的な実装方針を示します。

• 各要素 x に対し、x を含むリストへのポインターを配列で管理する
• Union(x, y)：一方のリストに含まれる要素を他方のリストにマージする
  • さらに、移動させたすべての要素に対して、リストへのポインターを更新する
  • 時間計算量は、移動させる要素の個数に比例し、最悪の場合 $O(n)$
• Find(x)：x を含む集合そのものを表すインスタンス、あるいはその ID を返す
  • 時間計算量は $O(1)$

Find 操作が $O(1)$ であるため、Quick Find と呼ばれるようです。
「集合に含まれる要素の一覧」にいつでも簡単にアクセスできるため、利用シーンによっては後述する木構造のものよりも使い勝手がよいことがあります。

さて、Union 操作を改善するために、次の工夫をします。

weighted-union heuristic

Union 操作において、何も考えずにリストの要素を移動させるだけでは最悪の場合 $O(n)$ 時間を要します。そこで、

• サイズ (要素の個数) が大きいほうのリストに、サイズが小さいほうのリストをマージする

という工夫を入れることで、すべてのリストが統合されるまでに $O(n \log n)$ 時間で済むようになり、したがって Union 操作の時間計算量はならしで $O( \log n)$ となります。

詳しくは "データ構造をマージする一般的なテク" とは？ を参照してください。
この「(大小の基準は状況に依存するが) 大きい集合に小さい集合をマージする」という手法は汎用性が高く、weighted-union heuristic と呼ばれるようです。

(2) 木構造による実装

素集合森 (disjoint-set forest) または Union-Find 木と呼ばれる実装で、辺により連結された木を集合と見なします。すなわち、Union 操作は辺を一つ追加することに相当します。また、それぞれの木の根を、集合を代表する要素と見なします。

まず、工夫を入れる前の基本的な実装方針を示します。

• 各要素 x に対し、x の親の ID を保持する
  • 根の親を -1 や null などで表すと決めておく
• Union(x, y)：一方の根と他方の根を親子関係として連結する
  • 内部で Find を呼び出すため、時間計算量は Find と同じオーダーになる
• Find(x)：x を含む木の根の ID を返す
  • 再帰関数を利用して根を探索する
  • 時間計算量は木の高さに比例し、最悪の場合 $O(n)$

これに「union by size」「union by rank」「経路圧縮」という工夫を組み合わせることで時間計算量を改善していきます。「union by size」と「union by rank」は上述の weighted-union heuristic の一種で、どちらかを選択することになります。したがって、次の 6 通りの実装の組合せが考えられます。

• 工夫なし
• union by size のみ
• union by rank のみ
• 経路圧縮 のみ
• union by size と 経路圧縮
• union by rank と 経路圧縮

union by size

Union 操作において、どちらの根を親として辺を追加するかが問題となりますが、リストによる実装のときと同様に考えて、

• サイズの大きい木に、サイズの小さい木をマージする
• すなわち、サイズの大きい木の根を親、サイズの小さい木の根を子として辺を追加する

という方針に従うのが union by size です。
これを実現するために、各木の根に対して、木のサイズを保持させます。木を連結するときには、新たな木の根となるほうのみサイズを更新すればよいです。
この工夫により木の高さは $O( \log n)$ となるため、Find 操作の時間計算量は $O( \log n)$ となります。

union by rank

ここでは「ランク」という概念を導入したいのですが、その意味を説明するために、先に木の高さについて考えます。

「union by size があるのだから、union by height もできそう」つまり「高い木に低い木をマージすれば、木の高さを $O( \log n)$ に保てそう」と自然に考えることができます。
実際これは正しいのですが、のちに説明する経路圧縮により、木の高さは動的に小さくなる可能性があります。このとき木の高さを厳密に再計算するにはすべての枝からの情報が必要となりますが、これを効率的に実行できそうにありません。

そこで、木の高さよりも条件を少し緩めて、かつ値を管理しやすくしたものが次の「ランク」です。

• ランクの定義：初期値は 0。ランクの等しい木同士を連結するときに限り、1 が加算される。

つまり、下がることのない値であると定めます。なお、木の高さが小さくならないのであれば、ランクは木の高さと同じです。そして、

• ランクの大きい木に、ランクの小さい木をマージする

という方針に従うのが union by rank であり、union by size のときと同様に、各木の根に対して、木のランクを保持させます。木を連結するときには、新たな木の根となるほうのみランクを更新すればよいです。
この方法でも木の高さを $O( \log n)$ に保つことができ、Find 操作の時間計算量は $O( \log n)$ となります。

経路圧縮

経路圧縮 (path compression) は、ある要素に対する Find 操作により根が判明したときに、根を直接の親と再設定することで次回以降の探索回数を削減する手法です。再帰関数を利用することで、途中で通るすべての要素に対しても処理できます。この手法により、Find 操作の時間計算量はならしで $O( \log n)$ となるようです。

工夫の組合せ

ここまでに説明した工夫を組み合わせ、「union by size と経路圧縮」または「union by rank と経路圧縮」を実装することで、Find 操作の時間計算量はならしで $O( \alpha (n))$ となります [7]。ここで、$\alpha (n)$ は逆アッカーマン関数であり、実用上は $5$ 未満の値です。計算量の証明は難解らしいです (よく知りません)。

以上により Union および Find 操作は非常に高速にできるようになりましたが、このような木構造では、例えば「集合に含まれる要素の一覧」を得るには別途、名寄せの処理が必要になります。

考察

根の親について
「根の親は根自身とする」という方針の資料も多いのですが、これは「自己ループの辺がある」という別の意味を持ってしまうと考えています。一般的なグラフにおいては行き止まりを無効な値で表すことが多いため、本記事では -1 や null などで表すこととしました。

サイズとランクについて
ランクという概念はあまり外部仕様としての意味を持ちませんが、各集合のサイズは使い道があり実用的です。そこで、個人的には「union by size と経路圧縮」の実装を採用しています。

「経路圧縮のみ」の場合の処理速度について
「経路圧縮のみ」の場合の時間計算量はならしで $O( \log n)$ と書きましたが、経験上は $O( \alpha (n))$ に近いと言ってよいほど速いです。

実装オプション

実装のオプションとして、次のようなものが考えられます。

• 要素の ID が任意のデータ型である場合
• データ拡張 (data augmentation)
  • 例えば、集合内の要素の最大値など

利用シナリオ

Union-Find は、グラフの連結判定、サイクル検出などに使うことができます。
また、最小全域木を求めるアルゴリズムの一つであるクラスカル法に応用されています。

問題集

• ALDS1_11_D 連結成分分解 (AOJ)
• ACL Beginner Contest C - Connect Cities
• ABC 177 D - Friends
• ARC 106 B - Values
• 競プロ典型 90 問 012 - Red Painting
• ABC 183 F - Confluence

参照

1. AtCoder Typical Contest 001 B - Union Find - 問題および解説
2. Union-Find木 (いかたこのたこつぼ)
3. Union-Find (プリンストン大学)
4. 素集合データ構造 (Wikipedia)
5. アルゴリズムイントロダクション 第3版 総合版 第21章
6. "データ構造をマージする一般的なテク" とは？
7. Robert E. Tarjan and Jan van Leeuwen. Worst-case Analysis of Set Union Algorithms. Journal of the ACM, 31(2):245–281, 1984
8. Union Find の計算量の話
9. AlgorithmLab (GitHub) - 筆者による実装サンプル (C#)