union_find
クラス · 素集合データ構造 (Union-Find)
struct union_find;
概要
素集合データ構造
Implement (union by size) + (path compression)
計算量
- 構築は $O(n)$、代表・連結判定・サイズ取得・併合は償却 $O(\alpha(n))$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空の Union-Find を作る (2) n 個の単集合を作る |
(1) $O(1)$ (2) $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
root |
x の代表を返し、経路圧縮する |
償却 $O(\alpha(n))$ |
get_root |
root(x) の別名 |
償却 $O(\alpha(n))$ |
is_root |
x が集合の代表なら true を返す |
$O(1)$ |
same |
x, y が同じ集合なら true を返す |
償却 $O(\alpha(n))$ |
is_same |
same(x, y) の別名 |
償却 $O(\alpha(n))$ |
rank |
現在の連結成分数を返す | $O(1)$ |
size |
x が属する集合の要素数を返す |
償却 $O(\alpha(n))$ |
get_size |
size(x) の別名 |
償却 $O(\alpha(n))$ |
leaders |
全ての集合の代表を返す | $O(n)$ |
unite |
(1) x, y の集合を併合する(2) x, y を併合し、代表と入れ替えの有無を f(x, y, swapped) に渡す(3) x, y を併合し、併合後の代表を f(x, y) に渡す |
(1) 償却 $O(\alpha(n))$ (2) 償却 $O(\alpha(n))$（ f の実行時間を除く）(3) 償却 $O(\alpha(n))$（ f の実行時間を除く） |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
(1) 頂点 x の内部表現を読み取り専用で返す(2) 頂点 x の内部表現を返す |
$O(1)$ |
メンバの詳細
(constructor)
// (1)
union_find() = default;
// (2)
explicit union_find(int _n);
(1) 空の Union-Find を作る
- 計算量: $O(1)$
(2) n 個の単集合を作る
- 計算量: $O(n)$
unite
// (1)
bool unite(int x, int y);
// (2)
template <class F>
requires std::invocable<F, int, int, bool>
bool unite(int x, int y, F f);
// (3)
template <class F>
requires std::invocable<F, int, int>
bool unite(int x, int y, F f);
(1) x, y の集合を併合する
- 戻り値: 新たに併合したなら true
- 計算量: 償却 $O(\alpha(n))$
(2) x, y を併合し、代表と入れ替えの有無を f(x, y, swapped) に渡す
- 戻り値: 新たに併合したなら true
- 計算量: 償却 $O(\alpha(n))$（
fの実行時間を除く）
(3) x, y を併合し、併合後の代表を f(x, y) に渡す
- 戻り値: 新たに併合したなら true
- 計算量: 償却 $O(\alpha(n))$（
fの実行時間を除く）
operator[]
// (1)
const int &operator[](std::size_t x) const;
// (2)
int &operator[](std::size_t x);
(1) 頂点 x の内部表現を読み取り専用で返す
- 計算量: $O(1)$
(2) 頂点 x の内部表現を返す
- 計算量: $O(1)$