dynamic_union_find

戻り値: 新たに併合したなら true
計算量: 期待償却 $O(\alpha(n))$（ f の実行時間を除く）

struct dynamic_union_find;

概要

64bit整数キーを必要時に追加する動的Union-Find

名前	説明	計算量
`(constructor)`	空の Union-Find を作る	$O(1)$

名前	説明	計算量
`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))$
`size`	`x` が属する集合の要素数を返す	期待償却 $O(\alpha(n))$
`get_size`	`size(x)` の別名	期待償却 $O(\alpha(n))$
`clear`	全てのキーと併合情報を削除する	$O(n)$
`unite`	(1) `x`, `y` の集合を併合し、新たに併合したかを返す (2) `x`, `y` を併合した後、代表 `x`, `y` を `f(x, y)` に渡す	(1) 期待償却 $O(\alpha(n))$ (2) 期待償却 $O(\alpha(n))$（`f` の実行時間を除く）

// (1)
bool unite(std::int64_t x, std::int64_t y);

// (2)
template <class F>
bool unite(std::int64_t x, std::int64_t y, F f);

(1) x, y の集合を併合し、新たに併合したかを返す

(2) x, y を併合した後、代表 x, y を f(x, y) に渡す

既に同じ集合なら同じ代表を 2 引数へ渡す。