Struct PotentialUnionFind

pub struct PotentialUnionFind<T> { /* private fields */ }

ポテンシャル付きUnionfind

Implementations

impl<T> PotentialUnionFind<T>

where T: AbelianGroup + Clone,

pub fn new_commutative(n: usize) -> Self

大きさnのPotentialUnionFindを生成する。(ポテンシャルが可換群のとき)

impl<T> PotentialUnionFind<T>

where T: Group + Clone,

pub fn new_non_commutative(n: usize) -> Self

大きさnのPotentialUnionFindを生成する。(ポテンシャルが可換とは限らない群のとき)

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

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

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

iのポテンシャル($P(i)$)を返す。

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

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

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

iとjが同一の素集合に属するとき、ポテンシャルの差($P(i) - P(j)$)を返す。

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

iの属する素集合とjの属する素集合を統合する。 統合後は、$P(i) = P(j) + p$を満たす。

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

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

pub fn count_groups(&self) -> usize

素集合の個数を返す。

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

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