Struct WeightedUnionFind

pub struct WeightedUnionFind<G: Abel> { /* private fields */ }

重み付きUnionFind

Implementations

impl<G: Abel> WeightedUnionFind<G>

where G::Val: Eq,

pub fn new(n: usize) -> Self

UnionFindを構築

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

根を求める

pub fn weight(&mut self, x: usize) -> G::Val

重みを求める

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

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

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

重みの差を求める

同じグループにいない場合にはNoneを返す

pub fn unite( &mut self, x: usize, y: usize, weight: G::Val, ) -> Result<bool, &str>

集合x,yをself.diff(x, y) = weightとなるように併合する．

戻り値

• すでにx,yが併合済みだった場合
  • self.diff(x, y) == weight の場合 → Some(false)
  • self.diff(x, y) != weight の場合 → Err(())
• x,yが併合済みでない場合 → Ok(true)

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

xが属する集合の大きさを求める

pub fn group_count(&self) -> usize

全体の要素数を求める