Struct PotentialUnionFind

pub struct PotentialUnionFind<G: Group> { /* private fields */ }

ポテンシャル付きUnionfind

Implementations

impl<G> PotentialUnionFind<G>

where G: AbelianGroup, G::Element: Clone,

pub fn new_commutative(group: G, n: usize) -> Self

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

impl<G> PotentialUnionFind<G>

where G: Group, G::Element: Clone,

pub fn new_non_commutative(group: G, n: usize) -> Self

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

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

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

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

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<G::Element>

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

pub fn merge(&mut self, i: usize, j: usize, p: G::Element) -> 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>>

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