Trait nekolib::traits::DisjointSet

pub trait DisjointSet {
    // Required methods
    fn new(n: usize) -> Self;
    fn len(&self) -> usize;
    fn unite(&mut self, u: usize, v: usize) -> bool;
    fn repr(&self, u: usize) -> usize;
    fn count(&self, u: usize) -> usize;

    // Provided methods
    fn is_empty(&self) -> bool { ... }
    fn equiv(&self, u: usize, v: usize) -> bool { ... }
    fn subset(&self, u: usize) -> Vec<usize> { ... }
    fn partition(&self) -> Vec<Vec<usize>> { ... }
}

共通要素を持たない集合族で、併合が可能なもの。

Required Methods

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$ を含む集合の要素数を返す。

Provided Methods

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>>

分割を返す。

$u$ が代表元のとき、$u$ 番目の Vec にそれと等価な要素たちが入る。

Implementors

impl DisjointSet for UnionFind