Struct disjoint_set::DisjointSet

pub struct DisjointSet<T: Clone> { /* fields omitted */ }

Tarjan's Union-Find Data structure

Methods

impl<T> DisjointSet<T> where
    T: Clone + Hash + Eq, 

fn new() -> Self

fn make_set(&mut self, x: T)

fn find(&mut self, x: T) -> Option<usize>

Returns Some(num), num is the tag of subset in which x is. If x is not in the data structure, it returns None.

fn union(&mut self, x: T, y: T) -> Result<usize, ()>

Union the subsets to which x and y belong. If it returns Ok, it is the tag for unified subset. it returns Err(), at least one of x and y is not in the disjoint-set.