Union Find
作成日：2019.01.17
最終更新日：2019.01.17
目次
できること
素集合データ構造の一種で、集合の併合(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))$であることを示した最初の論文。