Struct UnionFind 

pub struct UnionFind { /* private fields */ }

Disjoint-set forest with path compression and union by rank.

Examples

use u_numflow::collections::UnionFind;

let mut uf = UnionFind::new(5);
assert_eq!(uf.component_count(), 5);

uf.union(0, 1);
uf.union(2, 3);
assert_eq!(uf.component_count(), 3);

assert!(uf.connected(0, 1));
assert!(!uf.connected(0, 2));

uf.union(1, 3);
assert!(uf.connected(0, 2)); // transitivity
assert_eq!(uf.component_count(), 2);

Implementations

impl UnionFind

pub fn new(n: usize) -> Self

Creates a new Union-Find with n disjoint singleton sets {0}, {1}, ..., {n-1}.

Complexity

O(n)

pub fn len(&self) -> usize

Returns the number of elements.

pub fn is_empty(&self) -> bool

Returns true if there are no elements.

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

Finds the representative (root) of the set containing x.

Applies path compression: every node on the path from x to the root is made a direct child of the root.

Complexity

Amortized O(α(n))

Panics

Panics if x >= len().

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

Merges the sets containing x and y.

Uses union by rank: the tree with smaller rank is attached under the root of the tree with larger rank.

Returns

true if x and y were in different sets (and are now merged), false if they were already in the same set.

Complexity

Amortized O(α(n))

Panics

Panics if x >= len() or y >= len().

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

Returns true if x and y are in the same set.

Complexity

Amortized O(α(n))

pub fn component_count(&self) -> usize

Returns the number of disjoint sets.

Complexity

O(1)

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

Returns the size of the set containing x.

Complexity

Amortized O(α(n))

Trait Implementations

impl Clone for UnionFind

fn clone(&self) -> UnionFind

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for UnionFind

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.