Trait 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 にそれと等価な要素たちが入る。

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl DisjointSet for UnionFind