set.union_find

参考

set.union_find.cc

/*
 * 参考; http://www.prefield.com/algorithm/container/union_find.html
 */

struct UnionFind {
  vector<int> table;
  UnionFind(int size) : table(size, -1) {}
  int root(int x) {
    if (table[x] < 0) return x;
    table[x] = root(table[x]);
    return table[x];
  }
  bool merge (int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (table[y] < table[x]) swap(x, y);
      table[x] += table[y]; table[y] = x;
    }
    return x != y;
  }
};
 

set.union_find.rs

struct UnionFind { table: Vec<i32> }
impl UnionFind {

    fn new(n: usize) -> UnionFind {
        UnionFind { table: vec![-1; n], }
    }

    fn root(&mut self, x: i32) -> i32 {
        if self.table[x as usize] < 0 {
            x
        } else {
            let px = self.table[x as usize];
            let r = self.root(px);
            self.table[x as usize] = r;
            r
        }
    }

    fn merge(&mut self, x: i32, y: i32) {
        let mut rx = self.root(x) as usize;
        let mut ry = self.root(y) as usize;
        if rx != ry {
            if self.table[ry] < self.table[rx] { swap!(rx, ry) }
            self.table[rx] += self.table[ry];
            self.table[ry] = rx as i32;
        }
    }

    fn size(&mut self, x: i32) -> i32 {
        let r = self.root(x);
        return -self.table[r as usize]
    }

}