Struct UnionFind 

pub struct UnionFind { /* private fields */ }

Disjoint-set forest with path halving and union by size.

Implementations

impl UnionFind

pub fn new(n: usize) -> Self

Create n singleton sets.

Params

• n - Number of elements.

Returns

The initialised forest.

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

Find the root of x, halving the path on the way up.

Params

• x - Element to look up.

Returns

The root of x’s set.

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

Merge the sets containing a and b, smaller tree under larger.

Params

• a - First element.
• b - Second element.

Returns

true when the two were in different sets and have just been merged, false when they already shared a root. Kruskal needs that answer to decide whether an edge joins two components or closes a cycle.