Struct StreamingUnionFind 

pub struct StreamingUnionFind { /* private fields */ }

Online connected-components via path-compressed, union-by-rank Union-Find.

As edges arrive from the stream the structure is updated in O(α(n)) amortised time per edge (inverse Ackermann).

Implementations

impl StreamingUnionFind

pub fn new() -> Self

Create an empty Union-Find structure.

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

Find the representative of x with full path compression (iterative).

pub fn process_edge(&mut self, u: usize, v: usize)

Process edge (u, v) — union the two components.

pub fn n_components(&self) -> usize

Return the number of distinct connected components.

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

Return the canonical component identifier for x.

Trait Implementations

impl Debug for StreamingUnionFind

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for StreamingUnionFind

fn default() -> StreamingUnionFind

Returns the “default value” for a type.