Struct DisjointSet 

pub struct DisjointSet { /* private fields */ }

Union-Find (Disjoint Set Union) with path compression and union by rank.

Provides near-constant amortized time for find and union. The amortized cost per operation is O(α(n)) where α is the inverse Ackermann function.

Implementations

impl DisjointSet

pub fn new(n: usize) -> Self

Create a disjoint-set structure for n elements, each in its own set.

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

Find the representative (root) of the set containing element x.

Applies path compression for amortized efficiency.

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

Unite the sets containing x and y.

Returns true if they were in different sets, false if already united. Uses union by rank to keep trees shallow.

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

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

pub fn num_sets(&self) -> usize

Return the number of disjoint sets.