Union Find

作成日:2019.01.17
最終更新日:2019.01.17

目次

  1. 概要
  2. 原理
  3. 計算量
  4. 実装

できること

 素集合データ構造の一種で、集合の併合(union)と2つの要素が同じ集合に含まれるかの判定(find)をほぼ定数時間で行える。 また、他のデータ構造を持たせて同時に併合していくこともできる。
 本記事のコードでは、集合に含まれる要素の数や集合の個数(併合が起きた回数)もほぼ定数時間で求めることができる。

目次に戻る

所感

 グラフの連結成分ごとに考える時にはほとんど必要となる頻出のデータ構造である。 そのためUnion Findを使う問題では、しばしばグラフに落とし込むのが本質となる。

目次に戻る

出題実例、応用例

ARC083F : Collecting Balls本サイトでの解説
ARC093E : Bichrome Spanning Tree本サイトでの解説
ARC097D : Equals本サイトでの解説
ARC098F : Donation本サイトでの解説データ構造を乗せた実例

目次に戻る

参考

(*印は各節末にもあげた参考文献であることを表す)

プログラミングコンテストでのデータ構造 (slideshare by iwiwi)
 Union Find、平方分割、セグメントツリーの解説がなされている。
* "データ構造をマージする一般的なテク" とは? (blog by iwiwi)
 タイトルの通り。Union Findと同様の機能を持つWeighted Quick Findも説明されている。
UnionFindTree に関する知見の諸々 (blog by noshi91)
 Union Findの永続化など発展的な話題がまとめられている。
Graph Algorithms III: Union-Find (lecture by Carnegie Mellon University)
 Union Findのならし計算量が$O(\log^* N)$であることの解析がなされている。
* Analysis of Union-Find (lecture by Cornell University)
 Union Findのならし計算量が$O(\alpha(N))$であることの解析がなされている。
* Worst-Case Analysis of Set Union Algorithms (Tarjan,Leeuwen)
 経路圧縮の代わりにhalvingやsplittingを行った時の計算量解析もなされている。
Efficiency of a Good But Not Linear Set Union Algorithm (Tarjan)
 Union Findのならし計算量が$O(\alpha(N))$であることを示した最初の論文。

目次に戻る

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告