pub struct UnionFind<K> { /* private fields */ }
Expand description
UnionFind<K>
is a disjoint-set data structure. It tracks set membership of n elements
indexed from 0 to n - 1. The scalar type is K
which must be an unsigned integer type.
http://en.wikipedia.org/wiki/Disjoint-set_data_structure
Too awesome not to quote:
“The amortized time per operation is O(α(n)) where α(n) is the inverse of f(x) = A(x, x) with A being the extremely fast-growing Ackermann function.”
Implementations§
source§impl<K> UnionFind<K>where
K: IndexType,
impl<K> UnionFind<K>where
K: IndexType,
sourcepub fn find_mut(&mut self, x: K) -> K
pub fn find_mut(&mut self, x: K) -> K
Return the representative for x
.
Write back the found representative, flattening the internal datastructure in the process and quicken future lookups.
Panics if x
is out of bounds.
sourcepub fn equiv(&self, x: K, y: K) -> bool
pub fn equiv(&self, x: K, y: K) -> bool
Returns true
if the given elements belong to the same set, and returns
false
otherwise.
sourcepub fn union(&mut self, x: K, y: K) -> bool
pub fn union(&mut self, x: K, y: K) -> bool
Unify the two sets containing x
and y
.
Return false
if the sets were already the same, true
if they were unified.
Panics if x
or y
is out of bounds.
sourcepub fn into_labeling(self) -> Vec<K>
pub fn into_labeling(self) -> Vec<K>
Return a vector mapping each element to its representative.