Struct k0i::union_find::UnionFindTree

pub struct UnionFindTree { /* private fields */ }

Given the following tree structure 0 7 9 / \ / /
1 3 8 10 11 / / \
2 4 5 12 / 6

use k0i::union_find::UnionFindTree;
let tree = vec![(0,1),(0,3),(1,2),(3,4),(3,5),(2,6),(7,8),(9,10),(9,11),(11,12)];
let mut uft = UnionFindTree::new(13);
for (a,b) in tree{
    uft.unite(a,b);
}
assert!(uft.is_same(6,5));
assert!(uft.is_same(6,4));
assert!(uft.is_same(0,4));
assert!(uft.is_same(2,5));
assert!(uft.is_same(7,8));
assert!(uft.is_same(9,11));

assert_eq!(uft.is_same(0,9),false);
assert_eq!(uft.is_same(7,12),false);

assert_eq!(uft.size(0),7);
assert_eq!(uft.size(7),2);
assert_eq!(uft.size(9),4);

Implementations

impl UnionFindTree

pub fn new(n: usize) -> Self

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

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

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

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

Trait Implementations

impl Debug for UnionFindTree

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

Formats the value using the given formatter.