Disjoint Set Union / UnionFind
素集合データ構造 (Disjoint Set Union) / UnionFind
競プロにおいてはこの$ 2用語はもうほぼ区別されていない。
競プロにおいては
辺が無い$ N頂点のグラフを作り、以下のような操作が出来る。
以下を時間計算量 償却$ Ο(α(N))で行える。$ αについては 計算量のaについて を参照されたし。 グラフ上に新規に辺を張る
グラフ上の任意の$ 2頂点が現在、連結であるかを確認する。
この機能を実装するために、任意の$ 1頂点についてその代表たる頂点を返すこともできる。
AtCoder Library における実装では、更に以下の機能がある。
任意の$ 1頂点を指定して、その頂点が含まれる連結成分の大きさを求める。なお、時間計算量は償却$ Ο(α(N))である。
連結成分ごとに頂点を分けたリストを得る。時間計算量$ Ο(N)。
実装について
最初、$ N頂点$ 0辺の森が作られている。この森においてはもちろん各頂点がその連結成分の根である。 辺を足す度に、繋がれる頂点どうしのどちらかを根にして、もう片方は根でなくする。
なお、既に連結な頂点同士については何もしない。そうすることによって各連結成分が木である状態が常に保たれる。 このような実装においては、各頂点の代表を得るために時間計算量 償却$ Ο(N)を必要としてしまう。
ここで、辺を足すとき、繋がれる頂点どうしの大きさを比較して、大きい方の代表が根となるようにするだけで、辺を足す操作と、各頂点の代表を得る操作が時間計算量 償却$ Ο(\log N)となる。
加えて経路圧縮を行うことで、各操作の計算時間が償却$ Ο(α(N))となる。ACL における実装は当然ながらここまで高速化されている。
計算量の$ αについて
$ α(N)は逆アッカーマン関数であり、アッカーマン関数$ Aについて$ A(m-1, m-1) < n \leq A(m, m)ならば$ α(N)である。
$ α(2 \times 10^5)=4であり、ほぼ定数と見做せる。
余談
時々「UnionFind 木」と呼ばれているが、厳密には「UnionFind 森」になりそうである。