Struct UnionFind 

pub struct UnionFind { /* private fields */ }

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

This is the optimal data structure for incremental connectivity queries, providing nearly O(1) amortized operations.

Implementations

impl UnionFind

pub fn new(n: usize) -> Self

Creates a new Union-Find with n elements, each in its own set.

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

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

Uses path compression for amortized O(α(n)) complexity.

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

Unions the sets containing x and y.

Returns true if they were in different sets (union performed).

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

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