noshi91のメモ

データ構造のある風景

UnionFindTree に関する知見の諸々

2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。

2019/07/19 集合内の要素の列挙についての記述を追加しました。

はじめに

 UnionFindTree って知ってますか? 競プロでは恐らく最も使用頻度の高いデータ構造だと思います*1。この記事ではプログラミングコンテストで役に立つものから全く役に立たないものまで、UnionFindTree に関するいくつかの知見を書き留めておきます。記事の最後に各内容の実装例を貼っておきます。

 

計算量と実装のバリエーション

 UnionFindTree の操作辺りの計算量が O(α(N)) であることは良く知られていますが*2、この計算量を達成するアルゴリズムはいくつかのバリエーションがあります。併合時に木の高さと大きさのどちらを指標にするかというのは競プロ界隈でも比較的有名だと思います。これをそれぞれ「union by rank」「union by size」などと呼称します。経路圧縮の方にも「path compression」「path halving」「path splitting」という方法があり、それぞれに特徴があります。重要なのは、これらのいかなる選び方でも

・併合の工夫だけだと計算量は O(logN)

・経路圧縮だけだと計算量は O(logN)

・併合、経路圧縮両方をおこなうと O(α(N))

・(それぞれ致命的な定数倍の悪化などはない)

となることです。つまり、「好きなパーツを組み合わせて君だけの UnionFindTree を作ろう!」。ちなみに私は union by size + path halving が好きです。

Disjoint-set data structure - Wikipedia

 また、片方の工夫だけでも対数時間に収まることは忘れがちですが、UnionFindTree を応用するときに重要なので把握しておくことが望ましいです。

 

集合内の要素を列挙する

ある集合の全要素を線形時間で列挙したくなる場合があるかもしれません。そのままでは難しいですが (恐らく不可能) 、フィールドを追加し循環リストなどで管理することで達成できます。

noshi91.hatenablog.com

 

ポテンシャル付きUnionFindTree

  WeightedUnionFindTree 等と呼ばれているものです。ポテンシャル付きと呼ぶのは何人かの方が提案していて、私も気に入って使用しています。これは各要素に決められた値が不明な状態でいくつかの要素間の差分が分かるとき、その関係性を効率よく管理することが出来ます。AtCoder でもこれを使えばやるだけの問題が出ました。

D - People on a Line

一般にこのデータ構造は群を扱うことが出来るため、整数の単純な加算だけでなくxor演算などでも管理することができます。前述した path halving は相性が良く、path compression に比べて実装が単純になります。

 なお、集合間の距離が与えられる場合はモノイドも管理することが出来ます。これは以下の記事が詳しいです。

sigma425.hatenablog.com

記事内では "unionfindと同じオーダーで" とありますが、併合時の根を自由に決めることが出来ないので計算量は O(logN) に悪化します。

 

部分永続UnionFindTree

 UnionFindTree は親リンクを持つ探索木なので効率的な永続化が難しいのですが、部分永続化はとても効率的に実現することが出来ます。

noshi91.hatenablog.com

AGCや企業コンテスト、JOIなどで出題されており、恐らく前述の PotentializedUnionFindTree よりは使う機会があると思います。

 

全永続UnionFindTree

 二(四)分木の永続配列を使うことで自明に O(log^2N) になりますが、logN分木にすることで O(log^2N/loglogN) になり改善されます。O(logN) にする方法があるという論文を見た気がしたのですが、数か月前に挫折してから見失ってしまいました。ある種当然ですが、これにポテンシャルを乗せることもできます。乗せる乗せないに関わらず使う機会は永遠に来ないと思います。

 

要素を削除できるUnionFindTree

 構造と要素の指定を分離することで、平衡二分探索木のように削除(指定された要素を独立した状態に戻すこと)ができるようになります。これは以下の記事が詳しいです。

mojashi.hatenablog.com

しかし、これは実装する必要性が薄いです。削除する代わりに新しく要素を追加し、それを元の要素だと思って使用すれば普通の UnionFindTree でも実現できてしまいます。各操作ごとに極めて厳密な実行時間の制限があり、かつメモリを少しも無駄使い出来ない時には役に立つかもしれません。

 

辺を削除できるデータ構造

 辺を削除すると一気に難易度が上昇します。追加する辺に閉路が発生しない(=森を成す)ときは LinkCutTree や EulerTourTree で実現できます。計算量は少し重めの O(logN) *3 です。

プログラミングコンテストでのデータ構造 2 ~動的木編~

  辺が一般のグラフを成す場合さらに難しくなり、DynamicConnectivity 等と呼ばれるデータ構造が必要になります。

http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/17/Small17.pdf

 これらはかなりマニアックなコンテストでないと出題されないとは思いますが、実装が楽になる場合などがあるので持っていて損はしないと言えると思います。*4

 

RetroactiveUnionFind

 Retroactive なデータ構造とは、操作列に対する insert/erase が可能なデータ構造です。過去の操作を変更して現在の結果を得ることが出来るため、永続性とは異なる種類のクエリが可能になります。現在の結果のみを得られるものを PartiallyRetroactive、過去のいずれの地点での状態を得られるものを FullyRetroactive と呼びます。

Retroactive data structures - Wikipedia

UnionFind は LinkCutTree を用いることで FullyRetroactive にすることが出来ます。時間計算量は M を操作列長として O(logM) です。現在は競プロではほとんど見ませんが、今後注目される可能性はあると思います。

 

実装例

・UnionFindTree

NoshiMochiLibrary/UnionFind.noshi.cpp at master · noshi91/NoshiMochiLibrary · GitHub

・部分永続UnionFindTree

NoshiMochiLibrary/PartiallyPersistentUnionFind.noshi.cpp at master · noshi91/NoshiMochiLibrary · GitHub

・ポテンシャル付きUnionFIndTree

NoshiMochiLibrary/PotentializedUnionFind.noshi.cpp at master · noshi91/NoshiMochiLibrary · GitHub

・それ以外

 綺麗に実装出来たら載せます。全永続UnionFind以外は私以外の方のライブラリに存在を確認しています。

 

 

 

 

 

他にもあったら是非教えてください

 

 

 

*1:配列はメモリそのものと考えて除外します

*2:実際はunion,findそれぞれの操作回数によって評価されますが省略

*3:LinkCutTreeは償却

*4:全永続UFは本当に全然使いません