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

<details><summary>これまでと同じ前書き</summary><div>

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

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

</div></details>

---

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

- AtCoder Library の `dsu`
	- [ソースコード](https://github.com/atcoder/ac-library/blob/v1.3/atcoder/dsu.hpp)
	- [ドキュメント](https://github.com/atcoder/ac-library/blob/v1.3/document_ja/dsu.md)
- 参考文献
	- Zvi Galil and Giuseppe F. Italiano, <br>Data structures and algorithms for disjoint set union problems

## TL;DR

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

### 代表元を参照 `leader()` (find)
要素の所属グループを知るためのメソッドです。他のメソッドで頻繁にこれを利用しています。

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

```ruby
	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) かかる恐れがあります[^soe]。**グループの大きい方へ統合する**よう決めれば、パスの長さは最悪でも O(log N) に抑えられます（union by size）。

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

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

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

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

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

[^edge]: 多重辺や自己ループを含みます。
[^tree]: 木は様々な性質があるため、閉路を調べず判定する方法もあります。

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

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

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

言語にあるグループ分けするメソッドを利用する場合は楽に実装できます。例えば Ruby なら [`group_by`](https://docs.ruby-lang.org/ja/latest/method/Enumerable/i/group_by.html) を使って以下のように書けます。

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

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

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

### α(N)
α は[逆アッカーマン関数](https://ja.wikipedia.org/wiki/アッカーマン関数#逆アッカーマン関数)と呼ばれるものです。増加が log と比べ物にならないほど非常に遅く、仮に N = [10<sup>10<sup>100</sup></sup>](https://ja.wikipedia.org/wiki/グーゴルプレックス) であっても α(N) は 4 に収まります。なので O(α(N)) とあれば、 N が問題として現実的な大きさである限りは[^n-limit] **N が小さいときの数倍の時間**をみておけば対処できます。これはもはや定数時間とみて大丈夫です。

| N | log<sub>2</sub>N | log<sub>2</sub><sup>&lowast;</sup>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<sup>&lowast;</sup> は[反復対数](https://en.wikipedia.org/wiki/Iterated\_logarithm)です。指数表記を使わず書き下せる N の範囲ではこちらも十分にゆっくり増加します。

[^n-limit]: ACL のドキュメントには N ≦ 10<sup>8</sup> の制約が書いてあります。

### ならし
ならし計算量は[償却計算量](https://ja.wikipedia.org/wiki/償却解析)（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)) が得られます。