Union-Find とは？

最初は一人ずつ別のチームにして、必要に応じて合体させるイメージだよ。Findでチームの代表を調べ、二人の代表が同じなら同じチームと分かる。Unionは、その二人が属するチームを一つにまとめる操作なんだ。

各要素が親を持つ木を使う方法があるよ。親をたどって着く根が代表なんだ。チームを合体するときは、一方の根をもう一方につなぐ。サイズやランクを使って併合すれば、木が深くなりすぎるのを抑えられるよ。

Findで根を探すとき、通った経路を短くする工夫だよ。図の完全な経路圧縮では、CからBを経由してAに着いた後、Cの親をAにする。今回は通っていないDの親はBのまま。グループ全員を一度に根へつなぎ直す操作ではないよ。

経路圧縮とサイズやランクによる併合を組み合わせると、多数の操作をまとめて見た1操作当たりの計算量は償却O(α(n))になるよ。αはとてもゆっくり増える関数なので、実用上はほぼ定数のように扱われる。ただし、すべての1回の操作が最悪でもO(1)という意味ではなく、初期化の費用も別にあるんだ。

基本のUnion-Findには、分割や要素削除の操作はないよ。つながる辺を追加しながらグループを管理するような場面に向いている。クラスカル法でも、辺の両端が同じグループかを調べ、違うときに統合することで閉路を避けるんだ。