Struct DisjointSets 

pub struct DisjointSets(/* private fields */);

Disjoint sets over 0..n, the lowest member of a set its root, so a numbering derived from the roots depends on the elements’ order and on nothing else.

use arris_math::DisjointSets;

let mut sets = DisjointSets::new(5);
assert!(sets.union(3, 1));
assert!(sets.union(4, 3));
assert!(!sets.union(1, 4)); // already together
assert_eq!((sets.find(4), sets.find(3), sets.find(2)), (1, 1, 2));

Implementations

impl DisjointSets

pub fn new(n: usize) -> Self

n singletons.

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

The root of i’s set: its lowest member. Halves the path it walks.

Panics if i is not below the n of DisjointSets::new: an index is the caller’s own, never geometry.

pub fn union(&mut self, a: usize, b: usize) -> bool

Joins the sets of a and b; false if they were one already.

Trait Implementations

impl Clone for DisjointSets

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for DisjointSets

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

Formats the value using the given formatter.