Union-Find のリンク集
Union-Find について、参考になる記事や資料をまとめました。
Union-Find(素集合データ構造、DSU)は、互いに交わらない集合の族を管理し、「2 つの集合を併合する」「2 つの要素が同じ集合にあるか判定する」をほぼ定数時間で行えるデータ構造です。各集合を根つき木で表し、経路圧縮と union by size(または union by rank)の両方を使うと、1 回の操作がならし になります( は逆アッカーマン関数)。片方だけでも、ならし です。
まず読むもの
Section titled “まず読むもの”- Union find(素集合データ構造)(AtCoder、スライド)
- AtCoder Typical Contest 001 の B - Union Find の解説スライドです。集合を木で表す考え方から、経路圧縮・ランクによる高速化と C++ 実装までを図を中心に短く説明しています。
- 実装では配列名に
rankを使っているので、using namespace std;と一緒に書き写すとstd::rankと名前がぶつかることがあります。
- Union-Find Tree を理解する!素集合系を扱うデータ構造(アルゴリズムロジック)
- 素朴な実装から、経路圧縮、union by rank・union by size へと段階的に改良していく解説です。両方の C++ 実装と練習問題がそろっています。
- PythonでのUnion-Find(素集合データ構造)の実装と使い方(note.nkmk.me)
- Python での実装を段階的に作っていく記事です。グループの列挙などの便利なメソッドつきのクラスも載っています。
- 途中に出てくる経路圧縮だけの版は、要素数が多いと再帰の上限に当たることがあります。最後の完成形(union by size つき)なら問題ありません。
AtCoder Library(ACL)
Section titled “AtCoder Library(ACL)”- dsu のドキュメント
- 公式の仕様です。
mergeは新しい代表元を返し、groupsで連結成分をまとめて取り出せます。実装は union by size と経路圧縮の併用です(ソースのコメントに書かれています)。
- 公式の仕様です。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”- Union-Find の計算量上界
- 経路圧縮と union by size を併用したときの計算量が であることを証明する講座です。上級者向けです。
- アッカーマン関数,逆アッカーマン関数
- 上の講座の準備として、アッカーマン関数と逆アッカーマン関数の定義と、文献ごとの定義の違いを整理しています。
- 重み付き Union-Find とそれが使える問題のまとめ、および、牛ゲーについて(けんちょん)
- 要素どうしの差を管理する重み付き(ポテンシャル付き)Union-Find について、経路圧縮のときの重みの更新と、併合のときの補正を丁寧に説明しています。例題 4 問の解答と、不等式に広げた「牛ゲー」の話もあります。
- UnionFindTree に関する知見の諸々(noshi91のメモ)
- 計算量の組み合わせ(union by size/rank と経路圧縮などの組み合わせ)から、ポテンシャル付き、部分永続、全永続、要素の削除まで、発展的な話題を短く整理しています。
- Union Find(Luzhiled’s Library)
百科事典・英語の資料
Section titled “百科事典・英語の資料”- Disjoint-set data structure(英語版 Wikipedia)
- 経路圧縮・path halving・path splitting と union by size/rank の擬似コード、片方だけ使ったときと両方使ったときの計算量、歴史や変種まで網羅しています。右上の表の Search の最悪計算量が になっていますが、本文にあるとおり 1 回あたりの最悪は です。
- 素集合データ構造(日本語版 Wikipedia)
- 英語版の古い版をもとにした短い記事で、基本操作と union by rank・経路圧縮の擬似コードを日本語で確認できます。経路圧縮だけを使ったときの計算量は載っていません。
- Disjoint Set Union(cp-algorithms)
- 基本に加えて、偶奇つき Union-Find による二部グラフ判定、区間塗りのオフライン処理など、応用を幅広くまとめています。
- AtCoder Typical Contest 001 B - Union Find:基本操作の確認です。上のスライドが解説です。
- AtCoder Library Practice Contest A - Disjoint Set Union:上とほぼ同じ問題で、ACL の
dsuの使い方の確認です。 - Library Checker - Unionfind:上と同じ問題で、ライブラリの verify 用です。
- ABC177 D - Friends:連結成分の大きさを使います。
- ABC120 D - Decayed Bridges:辺を逆順に足していきます。
- ABC087 D - People on a Line:重み付き Union-Find の基本です。
- ABC049 D - 連結:Union-Find を 2 つ使い、代表元の組を数えます。
- ABC218 E - Destruction:クラスカル法で最小全域木を求めます。
- ABC065 D - Built?:辺の候補を絞ってからクラスカル法を使います。
- ABC040 D - 道路の老朽化対策について:クエリと辺をソートしてオフラインで処理します。
このブログの記事
Section titled “このブログの記事”- ABC478 E - lt and le
- 公式解説の方針を紹介する節で、同じ値になる頂点のグループを DSU でまとめています。