Struct DisjointSets

pub struct DisjointSets { /* private fields */ }

Represents a union of disjoint sets. Each set’s elements are arranged in a tree, whose root is the set’s representative.

Implementations

impl DisjointSets

pub fn new(size: usize) -> Self

Initializes disjoint sets containing one element each.

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

Finds the set’s representative. Do path compression along the way to make future queries faster.

pub fn merge(&mut self, u: usize, v: usize) -> bool

Merges the sets containing u and v into a single set containing their union. Returns true if u and v were previously in different sets.