#[derive(Copy, Clone, Debug, Hash)]
pub struct UnionFindSet {
parent: usize,
rank: usize,
}
impl UnionFindSet {
#[inline]
pub fn new(key: usize) -> UnionFindSet {
UnionFindSet {
parent: key,
rank: 0,
}
}
#[inline]
pub fn reinit(&mut self, key: usize) {
self.parent = key;
self.rank = 0;
}
}
pub fn find(x: usize, sets: &mut [UnionFindSet]) -> usize {
if sets[x].parent != x {
sets[x].parent = find(sets[x].parent, sets);
}
sets[x].parent
}
pub fn union(x: usize, y: usize, sets: &mut [UnionFindSet]) {
let x_root = find(x, sets);
let y_root = find(y, sets);
if x_root == y_root {
return;
}
let rankx = sets[x_root].rank;
let ranky = sets[y_root].rank;
if rankx < ranky {
sets[x_root].parent = y_root
} else if rankx > ranky {
sets[y_root].parent = x_root
} else {
sets[y_root].parent = x_root;
sets[x_root].rank = rankx + 1
}
}