AtCoder Library を読んでアルゴリズムを勉強：DSU（union-find）

これまでと同じ前書き

競技プログラミング AtCoder では、コンテストでよく使うアルゴリズムをライブラリにした AtCoder Library (ACL) を公開していて、特に C++ ならコンテスト内で利用できます。

私は Ruby を使っているため直接は利用できず、ライブラリを模写する必要がありました。その過程で学んだアルゴリズムを整理してまとめます。

---

今回は disjoint set union (DSU) です。 union-find や素集合データ構造の名称のほうが一般的なようです。グラフでのイメージがしやすく、アルゴリズムも読みやすく、勉強していて楽しかった記憶があります。（ACLの模写で最初に選びました）

• AtCoder Library の dsu
  • ソースコード
  • ドキュメント
• 参考文献
  • Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems

TL;DR

• 素集合系（disjoint sets）¹において、要素の属する集合の取得（find）・集合の統合（union）ができます
  • 無向グラフで辺をいくつか追加したときの、連結した頂点同士のグループを想像するといいです
• データ構造では、グループ毎に有向木の形になるよう表現します
  • 根の要素によってグループを識別します
  • find: ある要素から根を調べると、その所属グループがわかります
  • union: 根の間にリンクを張ると、グループを統合できます
  • 高速化のため、これらの操作にはそれぞれ工夫があります
• 時間計算量は実質 O(1) と考えておいていいです

利用場面

本来は「素集合データ構造」のアルゴリズムですが、 AtCoder で使うときは無向グラフの問題なことが多い印象です。

与えられた無向グラフについて、2つの頂点が連結である（辺をたどって移動できる）かどうかを調べられます。また連結グラフのみを考えたいとき、頂点をグループ分けすることで、連結グラフ毎に問題を考えられます。

グラフに辺が追加されていくような動的な場合でも、その時点での連結状況がすぐわかります。ただし辺を削除することには非対応です。

アルゴリズム

データ構造

集合の要素（元）を管理するため、要素数ぶんの長さの配列を用意します。集合の要素に 0 〜 N - 1 （あるいは 1 〜 N ）のIDが振られているとすれば、配列の添字と直接対応させられます。

配列の型は、任意の情報を持てるよう構造体を自作してもいいですが、最小限であれば配列の添字（＝集合の要素のID）を記録できる整数型で十分です。

---

集合の要素がどのグループに属しているかを示す方法として、そのグループの代表元を決めて表すことを考えます。代表元にはどの要素がなってもよく、統合時に適宜選びます²。

各要素が代表元を直接指し示せばすぐに所属グループがわかりますが、この規則ではグループの統合時に各要素を更新しなければならず大変です。そこで条件を緩め、代表元に辿り着くなら他の要素を指してもいいことにします。リンクの様子を有向グラフで表せば、各グループは根に向かう有向木となります。（この規則での統合方法は後述します）

代表元の持つデータ

代表元は他の要素を指さないので、そのことがわかるデータなら何を入れても構いません。

• 自分自身を指す
• -1 のような不正なIDを指す

後者を利用すると、そのグループに関する適当な情報を埋め込めます。 ACL では「グループに属する要素数」を符号反転して格納しています。単に要素数を知れる以上に、アルゴリズムの高速化に役立てられます。

初期化

一番最初の状態はグループの統合が全く行われていないので、「全ての要素が個別のグループに属している」となります。つまり全ての要素が代表元です。配列の各要素に、代表元を表すデータを格納しておきます。

代表元にグループの要素数を（マイナスで）記録する場合、最初はどのグループも要素数が 1 なので、 -1 を記録しておきます。

	def initialize(n)
		@elements = Array.new(n, -1)
	end

代表元を参照 leader() (find)

要素の所属グループを知るためのメソッドです。他のメソッドで頻繁にこれを利用しています。

各要素は代表元を「間接的に」指してよいと決めました。そのため一発では代表元に辿り着かず、再帰的に参照する必要があります。

	def leader(k)
		parent_index = @elements[k]
		parent_index < 0 ? k : leader(parent_index)
	end

高速化

これで代表元の参照という目的は果たせますが、辿るパスが長いと毎回時間がかかってしまいます。

そこで、代表元を参照し終わった際には指し示す先を代表元に更新してしまいます（path compression）。すると次回からは途中を完全にスキップできるようになります。

統合 merge() (union)

「2つの要素 a と b は同じグループ」という情報を反映し、グループを統合します。元から同じグループなら特にすることはありませんが、異なるグループだった場合は上手に纏める必要があります。

直接 a と b の間にリンクを張ってはいけません。例えば「 a ← b 」とした場合、確かにこれらの要素は同じグループになります。しかし、 b が元々いたグループの他の要素（特に代表元）はそのまま取り残されてしまい、グループ全体を統合できていません。

グループの全ての要素を纏めるには、代表元の間でリンクを張ります。こうすると、次回 leader() を呼び出せばこのリンクを伝って新しい代表元に到達できるようになります。

高速化

ここでリンクを張る方向を工夫する余地があります。雑に決めた場合（例えば第1引数側へ）、統合順序によってはパスが長くなり leader() のループで O(N) かかる恐れがあります³。グループの大きい方へ統合するよう決めれば、パスの長さは最悪でも O(log N) に抑えられます（union by size）。

その他

ACL では leader() を外から直接呼ばなくていいように、よくある用途をメソッド化してあります。

same()

2つの要素が同じグループに属しているかどうか判定します。単に両者の代表元が同じかどうか判定すればいいです。

無向グラフで色々な使い道があります。

• 頂点が同じグループの場合は連結であり、それらの頂点間にパスが存在することを表します。
• 連結な頂点間に辺⁴を追加すると閉路ができるため、 merge() で辺を追加する前に毎回チェックするとグラフに閉路があるかどうか検査できます。閉路が無いグラフは「森」であり、特に全ての頂点が連結している森は「木」です⁵。

size()

ある要素の属するグループの要素数を返します。代表元に要素数を格納しているならそれを参照するだけです。

groups()

要素をグループ毎に分類して返します。分かれていることだけが重要なので、結果の順序は不定です。

リストをサイズ指定して確保する場合は、多少の事前・事後作業が必要になります。

言語にあるグループ分けするメソッドを利用する場合は楽に実装できます。例えば Ruby なら group_by を使って以下のように書けます。

	def groups
		@elements.each_index
				.group_by { |k| leader(k) }
				.values
	end

付録：計算量について

ドキュメントでは計算量に「ならし O(α(N)) 」と書いてあります。

これは実用上は O(1) と考えて構いません。

α(N)

α は逆アッカーマン関数と呼ばれるものです。増加が log と比べ物にならないほど非常に遅く、仮に N = 10¹⁰¹⁰⁰ であっても α(N) は 4 に収まります。なので O(α(N)) とあれば、 N が問題として現実的な大きさである限りは⁶ N が小さいときの数倍の時間をみておけば対処できます。これはもはや定数時間とみて大丈夫です。

N	log2N	log2∗N	α(N)	備考
1	0	0	0
2	1	1	1
4	2	2	2	α(3) = 1
8	3	3	3	α(7) = 2
16	4	3	3
64	6	4	4	α(61) = 3
256	8	4	4
65536	16	4	4
4294967296	32	5	4
2 ** 65536	65536	5	4
2 ** 2 ** 65536	2 ** 65536	6	4
2 ** 2 ** 2 ** 65536	2 ** 2 ** 65536	7	5	α(N-3) = 4

※ α の定義は文献によって変えてあったり2変数だったりするため、上の表とずれることがあります。それでも「増加がとてつもなく遅い」性質は同じで、通常 4 を超えないと考えて大丈夫です。

※ log^∗ は反復対数です。指数表記を使わず書き下せる N の範囲ではこちらも十分にゆっくり増加します。

ならし

ならし計算量は償却計算量（amortized complexity）とも言います。同じ操作を繰り返す際に、たまに重いときがあるものの全体を通すと軽いときが多い場合、負荷を分配して見積もることで実際の使用感に近い計算量を出せます。

find は（高さを上手に抑えた）有向木を根まで辿る操作なので、最良で O(1) 、最悪で O(log N) かかります。しかし実際の問題で利用してみると、最悪計算量 O(log N) が実行時間に効いてくることはありません。例えば find を N 回実行する問題では、 O(N log N) になるケースは無くほぼ O(N) で済みます。

• find にパスを更新する高速化があるため、最悪ケースでの実行回数は限られます
• この最悪ケースを用意するには、 union を N - 1 回実行しておく必要があります
• → O(log N) のケース数回の実行時間は、 O(N) 以上の準備時間に埋もれてしまいます

計算量をより現実的に見積もるために、先行研究では「 union を n 回、 find を m 回」実行した場合の最悪ケースを求めています。その答えは O(n + m α(m + n, n)) だそうです。ここから1回あたりの平均を求めれば O(α(N)) が得られます。

1. 2つの集合が重ならない（両方に含まれる要素が存在しない）とき「互いに素」と言います。 ↩

2. 統合の適用順序を変えると、最終的なグループ分けは常に同じですが、代表元は同じとは限りません。 ↩

3. 単純に遅いことに加え、再帰ではスタックオーバーフローを起こす危険性があります。 ↩

4. 多重辺や自己ループを含みます。 ↩

5. 木は様々な性質があるため、閉路を調べず判定する方法もあります。 ↩

6. ACL のドキュメントには N ≦ 10⁸ の制約が書いてあります。 ↩