Union Find
作成日：2019.01.17
最終更新日：2019.01.17
目次
原理
集合を根付き木で表して、素集合たちを森として表現することを考える。
根をその集合の代表となる要素とすれば、findは親を根までたどって比較すればでき、unionは2つの集合を表す根を辺で結べばできる。
いずれも根までたどることになるので、これが高速にできるようにしたい。
何も工夫せずにやると、最悪の場合で木が直線状になり$O(N)$かかってしまう。
しかしこれは、辺のつなぎ方の工夫や経路圧縮をすることで改善できる。
まず、低くない方の木の根が他方の根の親になるように辺をつなげば、木の高さを$\lfloor \log N \rfloor$で抑えられる。
これは高さ$h(\geq 1)$にするには高さ$h-1$の木を2つつなぐ必要があることを考えると、高さ$h$の木には少なくとも$2^h$個の要素が含まれることが帰納的に分かるからである。
一方、高さの代わりに要素数を見ても良い。高さが増える時は低くない方の木が要素数の少ない木であり、新たな木の要素数はその倍以上になるから、高さ$h$の木には少なくとも$2^h$個の要素が含まれることが分かる。
木の高さが必要になることはないが、集合の要素数が知りたくなる場面はそれなりにある。
よって要素数で辺のつなぎ方を決めるようにすれば、余分な情報を持たずに有用な情報を得られるようになる。
さらに根を調べる時にたどった要素をすべて根につなぎなおす経路圧縮を行うと、次にそれらの要素について調べる時に二度手間にならない。
経路圧縮は要素を参照した時に親の要素番号を変えるだけだから、定数倍を除けば計算量は増えない。
注：経路圧縮の代わりにhalvingやsplittingという方法を用いても同じ計算量を達成できる。
データ構造をマージする一般的なテク(Quick Find Weighted)
集合に番号を割り振り、各要素がその番号を保持するという方法も考えられる。
するとfindは番号を見るだけで$O(1)$となる。
unionは併合する2つの集合のうち片方の番号を他方に付け替えればできる。
何も考えずにやると$O(N)$になるが、要素数の少ない方の集合の番号を付け替えることにすると、ならし計算量が$O(\log N)$になる。
これは各要素において、番号がつけ変わるたびに所属する集合の大きさが倍以上になることから分かる。
このアルゴリズムは「Quick Find Weighted」と呼ばれる。
同様に何かを併合する時に要素数が少ない方の要素を要素数が多い方に入れるようにすると、ならし計算量が併合処理にかかる計算量の$\log N$倍になる。
これは「データ構造をマージする一般的なテク」、あるいは単に「マージテク」と呼ばれる。
Union Findにデータ構造を乗せて集合と同時に併合していく時は、マージテクを用いる。
参考："データ構造をマージする一般的なテク" とは？ (blog by iwiwi)