Struct UnionFindMonoid

pub struct UnionFindMonoid<M: CommutativeMonoid> { /* private fields */ }

UnionFind木（モノイド）

Implementations

impl<M: CommutativeMonoid> UnionFindMonoid<M>

pub fn root(&mut self, x: usize) -> usize

根を求める

pub fn value(&mut self, x: usize) -> &M::Val

ノードxが属する集合の値を取得

pub fn is_same(&mut self, x: usize, y: usize) -> bool

同一の集合に所属するか判定

pub fn unite(&mut self, x: usize, y: usize) -> Option<usize>

集合x,yを併合する．

戻り値

• すでに併合済みだった場合None，そうでない場合親となった要素の番号を返す

pub fn get_size(&mut self, x: usize) -> usize

連結成分の大きさを求める

pub fn group_count(&self) -> usize

連結成分の数を返す

pub fn enum_groups(&mut self) -> HashMap<usize, Vec<usize>>

{代表元: 集合} のマップを返す

• 時間計算量: $O(N)$

impl UnionFindMonoid<()>

pub fn new(n: usize) -> Self

新しいUnionFind木を生成する

Trait Implementations

impl<M> Debug for UnionFindMonoid<M>

where M: CommutativeMonoid, M::Val: Debug + Clone,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<M: CommutativeMonoid> From<Vec<<M as Monoid>::Val>> for UnionFindMonoid<M>

fn from(value: Vec<M::Val>) -> Self

Converts to this type from the input type.

impl<M: CommutativeMonoid> FromIterator<<M as Monoid>::Val> for UnionFindMonoid<M>

fn from_iter<T: IntoIterator<Item = M::Val>>(iter: T) -> Self

Creates a value from an iterator.