Struct nekolib::ds::PotentializedUnionFind

pub struct PotentializedUnionFind<G: CommutativeGroup>where
    <G as Magma>::Set: Clone,{ /* private fields */ }

ポテンシャルつき union-find。

Idea

通常の union-find に加え、配列 pot を管理する。 親ノード par と子ノード child に対して、pot[child] には phi(child) - phi(par) を持つようにする。

代表元を探してパスを縮約する際、ポテンシャル差の更新を適切に行う。

Implementations

impl<G: CommutativeGroup> PotentializedUnionFind<G>where <G as Magma>::Set: Clone,

pub fn with_len(n: usize) -> Selfwhere G: Default,

Trait Implementations

impl<G: Clone + CommutativeGroup> Clone for PotentializedUnionFind<G>where <G as Magma>::Set: Clone,

fn clone(&self) -> PotentializedUnionFind<G>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<G: CommutativeGroup> PotentialFunction for PotentializedUnionFind<G>where <G as Magma>::Set: Clone,

type Item = G

要素の型。

fn new(n: usize, cgroup: G) -> Self

要素数 $n$ の集合 $\{0, 1, \dots, n-1\}$ で初期化する。

fn len(&self) -> usize

集合の要素数 $n$ を返す。

fn relate(&mut self, u: usize, v: usize, w: G::Set) -> Result<bool, G::Set>

ポテンシャルの差を定義する。

fn diff(&self, u: usize, v: usize) -> Option<G::Set>

ポテンシャルの差を求める。

fn repr_diff(&self, u: usize) -> (usize, G::Set)

代表元とのポテンシャルの差を求める。

fn is_empty(&self) -> bool

集合が空であれば true を返す。