Union Find
(data-structure/unionfind/union_find.hpp)
Description
Union find (disjoint set union, 素集合データ構造) は,素集合を管理するデータ構造である.
空間計算量: $O(n)$
Operations
-
UnionFind(int n)
- サイズ
n
の union find を構築する.
- 時間計算量: $O(n)$
-
int find(int x)
- $x$ が属する木の根を返す
- 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$
-
void unite(int x, int y)
- $x$ が属する集合と $y$ が属する集合を連結する
- 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$
-
bool same(int x, int y)
- $x$ と $y$ が同じ集合に属するかを判定する
- 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$
-
int size(int x)
- $x$ が属する集合の大きさを返す
- 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$
Note
$\alpha(x)$ は逆アッカーマン関数である.
この実装では高速化に path compression と union by size を用いている.どちらか一方だと計算量は $O(\log n)$ になるが,両方使用することで $O(\alpha(n))$ になる.path compression の代わりに path splitting や path halving,union by size の代わりに union by rank といった実装手法もあり,どれも同じ計算量を実現する.
Reference
Required by
Verified with
Code
Back to top page