Struct UnionFind 

pub struct UnionFind { /* private fields */ }

Implement union-find for elements with indices [0, …, N-1].

Implementations

impl UnionFind

pub fn new(size: i32) -> UnionFind

Create new union-find data where initially each element is a separate component.

pub fn representative(&mut self, element: i32) -> i32

Return the index of the current representative of the component the element belong to.

This mutates the data, as it needs to modify the representatives to short-cut further lookups.

pub fn merge(&mut self, left: i32, right: i32)

Merge the two distinct components the left and right elements belong to.

pub fn components(&self) -> i32

The current number of distinct components.

pub fn finalize(&mut self)

Collect the final root representatives of the components.

This must be called once, after all merging were done. Once it was called, it is no longer possible to perform any more merged.

pub fn component(&mut self, element: i32) -> i32

Return the index of the component the element belongs to.

Component indices are [0, …, M-1] for some small M, as opposed to representatives This may only be invoked after finalize has been called.