Struct DisjointSet 

pub struct DisjointSet { /* private fields */ }

Union-Find with union by rank and path halving.

Standard disjoint set forest supporting near-constant-time find and union operations (amortised inverse Ackermann). Used internally for connected component tracking during clustering.

Implementations

impl DisjointSet

pub fn new(n: usize) -> Self

Create a new disjoint set with n elements, each in its own singleton set.

Params

• n - Number of elements (indexed 0..n)

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

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

Applies path halving: each traversed node is repointed to its grandparent, flattening the tree over successive calls.

Params

• x - Element to look up

Returns

Root index of the component containing x

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

Merge the sets containing x and y by rank.

The shorter tree is attached under the taller one to keep depth bounded.

Params

• x - First element
• y - Second element

Returns

true if x and y were in different sets (i.e. a merge actually happened), false if they were already connected.

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

Check whether x and y belong to the same set.

Params

• x - First element
• y - Second element

Returns

true if both elements share the same root