PartiallyPersistentUnionFind

struct PartiallyPersistentUnionFind;

概要

過去の任意時刻を参照できる部分永続 Union-Find

名前	説明	計算量
`(constructor)`	`n` 個の単集合を時刻 0 の状態として作る	$O(n)$

名前	説明	計算量
`root`	(1) 現在時刻における `x` の代表を返す (2) 時刻 `t` における `x` の代表を返す	$O(\log n)$
`get_root`	`root(x, t)` の別名	$O(\log n)$
`is_root`	時刻 `t` に `x` が集合の代表なら true を返す	$O(1)$
`same`	(1) 現在時刻に `x`, `y` が同じ集合なら true を返す (2) 時刻 `t` に `x`, `y` が同じ集合なら true を返す	$O(\log n)$
`is_same`	`same(x, y, t)` の別名	$O(\log n)$
`size`	(1) 現在時刻に `x` が属する集合の要素数を返す (2) 時刻 `t` に `x` が属する集合の要素数を返す	$O(\log n)$
`get_size`	`size(x, t)` の別名	$O(\log n)$
`unite`	時刻を 1 進めて `x`, `y` の集合を併合する	$O(\log n)$

// (1)
int root(int x) const;

// (2)
int root(int x, int t) const;

(1) 現在時刻における x の代表を返す

(2) 時刻 t における x の代表を返す

// (1)
bool same(int x, int y) const;

// (2)
bool same(int x, int y, int t) const;

(1) 現在時刻に x, y が同じ集合なら true を返す

(2) 時刻 t に x, y が同じ集合なら true を返す

// (1)
int size(int x) const;

// (2)
int size(int x, int t) const;

(1) 現在時刻に x が属する集合の要素数を返す

(2) 時刻 t に x が属する集合の要素数を返す

bool unite(int x, int y);

時刻を 1 進めて x, y の集合を併合する