コンテンツにスキップ

Union-Find

タグ「Union-Find」の記事 1 件

Union-Find のリンク集

Union-Find について、参考になる記事や資料をまとめました。

Union-Find(素集合データ構造、DSU)は、互いに交わらない集合の族を管理し、「2 つの集合を併合する」「2 つの要素が同じ集合にあるか判定する」をほぼ定数時間で行えるデータ構造です。各集合を根つき木で表し、経路圧縮と union by size(または union by rank)の両方を使うと、1 回の操作がならし O(α(n))O(\alpha(n)) になります(α\alpha は逆アッカーマン関数)。片方だけでも、ならし O(log⁡n)O(\log n) です。

  • 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 つき)なら問題ありません。
  • dsu のドキュメント
    • 公式の仕様です。merge は新しい代表元を返し、groups で連結成分をまとめて取り出せます。実装は union by size と経路圧縮の併用です(ソースのコメントに書かれています)。
  • Union-Find の計算量上界
    • 経路圧縮と union by size を併用したときの計算量が O(N+Qα(N))O(N + Q\alpha(N)) であることを証明する講座です。上級者向けです。
  • アッカーマン関数,逆アッカーマン関数
    • 上の講座の準備として、アッカーマン関数と逆アッカーマン関数の定義と、文献ごとの定義の違いを整理しています。
  • Union Find(Luzhiled’s Library)
    • 短くて読みやすい C++ 実装で、各関数の計算量が日本語で書かれています。同じライブラリに、重み付き、undo 付き、部分永続などの派生版もあります。
    • 部分永続版のドキュメントは find を O(α)O(\alpha) としていますが、経路圧縮をしていないので、実際は O(log⁡n)O(\log n) です。
  • Disjoint-set data structure(英語版 Wikipedia)
    • 経路圧縮・path halving・path splitting と union by size/rank の擬似コード、片方だけ使ったときと両方使ったときの計算量、歴史や変種まで網羅しています。右上の表の Search の最悪計算量が O(α(n))O(\alpha(n)) になっていますが、本文にあるとおり 1 回あたりの最悪は Θ(log⁡n)\Theta(\log n) です。
  • 素集合データ構造(日本語版 Wikipedia)
    • 英語版の古い版をもとにした短い記事で、基本操作と union by rank・経路圧縮の擬似コードを日本語で確認できます。経路圧縮だけを使ったときの計算量は載っていません。
  • Disjoint Set Union(cp-algorithms)
    • 基本に加えて、偶奇つき Union-Find による二部グラフ判定、区間塗りのオフライン処理など、応用を幅広くまとめています。
  • ABC478 E - lt and le
    • 公式解説の方針を紹介する節で、同じ値になる頂点のグループを DSU でまとめています。