Struct Dsu 

pub struct Dsu { /* private fields */ }

Disjoint-set union (DSU) data structure.

Example

let mut dsu = Dsu::new(5);

for i in 0..5 {
    assert_eq!(dsu.find(i), i);
    assert_eq!(dsu.set_size(i), 1);
}

assert!(dsu.union(0, 1));
assert!(dsu.union(1, 2));
assert!(!dsu.union(0, 2));
assert!(dsu.union(3, 4));

assert_eq!(dsu.find(0), dsu.find(1));
assert_eq!(dsu.find(0), dsu.find(2));
assert_eq!(dsu.set_size(0), 3);

assert_eq!(dsu.find(3), dsu.find(4));
assert_eq!(dsu.set_size(3), 2);
assert_ne!(dsu.find(0), dsu.find(3));

assert!(dsu.union(1, 3));
assert_eq!(dsu.set_size(0), 5);
for i in 1..5 {
    assert_eq!(dsu.find(0), dsu.find(i));
}

Implementations

impl Dsu

pub fn new(n: usize) -> Self

Creates a new disjoint-set union data structure with n elements.

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

Find the root of the set containing the element at index x.

This requires &mut self because it performs path compression, making later calls faster.

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

Merges the sets containing index a and b.

Returns true if the sets were merged, false if they were already in the same set.

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

Returns the size of the set containing the element at index x.

This requires &mut self because it performs path compression, making later calls faster.

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

Returns the size of the set with root x.

This function will panic if x is not a root.

pub fn roots(&self) -> impl Iterator<Item = usize> + '_

Returns an iterator over the roots of the disjoint-set.

Trait Implementations

impl Debug for Dsu

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

Formats the value using the given formatter.