Struct nekolib::ds::UnionFind

pub struct UnionFind { /* private fields */ }

union-find。

Complexity

演算	時間計算量
new	$\Theta(n)$
unite	amortized $O(\alpha(n))$
repr	amortized $O(\alpha(n))$
equiv	amortized $O(\alpha(n))$
count	amortized $O(\alpha(n))$
subset	$\Theta(n)$

より tight には、$n$ 要素 $m$ クエリのとき、$O(m\cdot\alpha(m, n)+n)$ 時間となる。 ただし、$\alpha(m, n)$ は次のように定義される。 $$ \alpha(m, n) = \min\{k\in\mathbb{N}\mid J_k(\lfloor\log_2(n)\rfloor)\le 1+m/n\}. $$ ここで、$g^\diamond = (\lceil{\log_2}\rceil\circ g)^\star$ とし、$J_0(r) = \lceil(r-1)/2\rceil$, $J_k(r)=J_{k-1}^\diamond(r)$ ($k\gt 0$) である。 より直感的には、${\underbrace{J_0^{\diamond\diamond\cdots\diamond}}_{k\text{ many }\diamond{\text{s}}}}(\lfloor\log_2(n)\rfloor)$ が $1+m/n$ 以下になる最小の $k$ が $\alpha(m, n)$ である。

Complexity analysis

参考文献ふたつめの PDF の概略を書く。todo!()

これらより、$f(m, n, r)\le (\alpha(m, n)+2)\cdot m+2n$ が言える。

Note: $\alpha'(m, n) = \min\{k\in\mathbb{N}\mid \alpha_k(n)\le 3\}$ として $\alpha(m, n) = O(\alpha'(m, n))$ である。

Examples

use nekolib::traits::DisjointSet;
use nekolib::ds::UnionFind;

let mut uf = UnionFind::new(4);
assert!(!uf.equiv(0, 2));
uf.unite(0, 1);
uf.unite(1, 2);
assert!(uf.equiv(0, 2));
assert!(!uf.equiv(0, 3));
assert_eq!(uf.count(0), 3);

References

• http://www.gabrielnivasch.org/fun/inverse-ackermann
• http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf

Trait Implementations

impl Clone for UnionFind

fn clone(&self) -> UnionFind

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl DisjointSet for UnionFind

fn new(n: usize) -> Self

集合族を $\{\{0\}, \{1\}, \dots, \{n-1\}\}$ で初期化する。

fn len(&self) -> usize

集合族全体に含まれる要素数 $n$ を返す。

fn unite(&mut self, u: usize, v: usize) -> bool

$u$ を含む集合と $v$ を含む集合を併合する。 集合族に変化があれば true を返す。 $u$ と $v$ が元々同じ集合に含まれていれば false を返す。

fn repr(&self, u: usize) -> usize

$u$ を含む集合の代表元を返す。

fn count(&self, u: usize) -> usize

$u$ を含む集合の要素数を返す。

fn is_empty(&self) -> bool

集合族が空であれば true を返す。

fn equiv(&self, u: usize, v: usize) -> bool

$u$ と $v$ が同じ集合に含まれていれば true を返す。

fn subset(&self, u: usize) -> Vec<usize>

$u$ を含む集合の要素を列挙する。

fn partition(&self) -> Vec<Vec<usize>>

分割を返す。