Union Find(Disjoint Set Union)
(data-structure/union-find.hpp)
- View this file on GitHub
- Last update: 2024-08-10 13:03:16+09:00
- Include:
#include "data-structure/union-find.hpp"
Union-Find Tree(Disjoint Set Union)
概要
Union-Find Treeとは、素集合データ構造に対して
- 頂点$x,y$が属している二つの集合をマージする
- 頂点$x,y$が同じ集合に属しているかを判定する
という二つの操作をともに$\mathrm{O}(\alpha(n))$で高速に実行するライブラリである。($\alpha(n)$はアッカーマン関数$A(n, n)$の逆関数)
使い方
-
UnionFind(int sz)
:サイズ$sz$のUnionFindを生成する。計算量$\mathrm{O}(1)$ -
unite(int x, int y)
:xとyをマージする。返り値はマージに成功したらtrue
、失敗したらfalse
を返す。計算量$\mathrm{O}(\alpha(n))$($n$はUnionFindのサイズ) -
find(int k)
:kの根を返す。計算量$\mathrm{O}(\alpha(n))$ -
same(int x, int y)
:xとyが同じ連結成分に所属しているかを返す。計算量$\mathrm{O}(\alpha(n))$ -
size(int k)
:xを含む連結成分のサイズを返す。
Required by
- graph/functional-graph.hpp
- graph/kruskal.hpp
- graph/minimum-cost-arborescence.hpp
- Functional Graph(なもりグラフ)の分解 (graph/namori.hpp)
Verified with
- verify/verify-aoj-dsl/aoj-dsl-1-a.test.cpp
- verify/verify-aoj-grl/aoj-grl-2-a.test.cpp
- verify/verify-aoj-other/aoj-2821.test.cpp
- verify/verify-aoj-other/aoj-2891-2.test.cpp
- verify/verify-aoj-other/aoj-2891.test.cpp
- verify/verify-aoj-other/aoj-2995.test.cpp
- verify/verify-unit-test/parallel-union-find.test.cpp
- verify/verify-unit-test/tree-path.test.cpp
- verify/verify-yosupo-graph/yosupo-directed-mst.test.cpp
- verify/verify-yuki/yuki-1170-divide-interval.test.cpp
- verify/verify-yuki/yuki-1254-2.test.cpp
- verify/verify-yuki/yuki-1254.test.cpp
- verify/verify-yuki/yuki-1303.test.cpp
- verify/verify-yuki/yuki-2588.test.cpp