Struct UnionFind

pub struct UnionFind<'a, T = ()> { /* private fields */ }

素集合の統合と所属の判定ができるデータ構造。

Implementations

impl UnionFind<'_, ()>

pub fn new(n: usize) -> Self

大きさ1の集合をn個用意する。

impl<'a, T> UnionFind<'a, T>

pub fn with_values(values: Vec<T>, merge: Box<impl 'a + Fn(T, T) -> T>) -> Self

大きさ1の集合を|values|個用意する。このとき、各集合iにvalue[i]を割り当てる。

mergeは、集合を統合する際に、新しい集合に割り当てる値を返す。

pub fn root_of(&self, i: usize) -> usize

iの属する集合の根を返す。

pub fn is_same(&self, i: usize, j: usize) -> bool

iとjが同じ集合に属するならばtrueを返す。

pub fn merge(&mut self, i: usize, j: usize) -> usize

iの属する集合とjの属する集合を統合する。

pub fn size_of(&self, i: usize) -> usize

iの属する集合の大きさを返す。

pub fn count_groups(&self) -> usize

素集合の個数を返す。

pub fn value_of(&self, i: usize) -> Option<&T>

iの属する集合のもつ値を返す。

pub fn get_groups(&self) -> Vec<Vec<usize>>

素集合をすべて列挙する。