Learning Union-Find

What is Union-Find?

Union-Find is a data structure to manage groups in a tree structure.
When grouping in a tree structure, the advantage is that the following two points can be done quickly

1. Check if x and y exist in a same group or not.
2. If x and y exist in the same group, the affiliations of group x and group y can be easily merged.

Try to make Union-find Structure with Rust

struct UnionFind {
    par: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        let mut par = vec![0; n];
        for i in 0..n {
            par[i] = i;
        }
        return Self { par };
    }

    fn root(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            return x;
        }
        self.par[x] = self.root(self.par[x]);
        self.par[x]
    }

    fn unite(&mut self, x: usize, y: usize) {
        let rx = self.root(x);
        let ry = self.root(y);
        if rx == ry {
            return;
        }
        self.par[rx] = ry;
    }

    fn same(&mut self, x: usize, y: usize) -> bool {
        let rx = self.root(x);
        let ry = self.root(y);
        rx == ry
    }
}

• par: par[a] = b means "a's parent is b"
• new: This function initializes everything as roots.
• root: This function returns root.

For examples

• When data x is a root, it returns x

• When data x is not a root, par recursively traces back to the parent and return parental with

• unite:
  This function merges two trees that don't have the same root.

• same:
  This function return true if x and y have the same root.