Union Findのrust記事と簡単な理解

Union Findに関して

下記を見るのが一番早い
https://atcoder.jp/contests/atc001/tasks/unionfind_a
C++ではなくrustで実装されているものを探した。

rust実装

こちらのコードを丸パクリ
https://quantized-cube.com/rust-union-find/

また、使い方を勉強するため試しに
下記の問題の入力例を突っ込んでみて、その時のそれぞれの関数が何が出力されるかを見た
https://atcoder.jp/contests/abc177/tasks/abc177_d

今回の場合は
{1,2,5}と{3,4}がグループになる
この実装だとグループにしたのが早いほうが根になる。
rootだと根、それぞれ1,3が出力され
sizeはそれぞれ3,2となり
issameで同じグループにいるかどうか確認するといった流れのようだ。
parがグループわけの記録
sizがグループのサイズみたい。

use proconio::{input};
// Union-Find
pub struct UnionFind {
    par: Vec<i64>,
    siz: Vec<u64>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        Self {
            par: vec![-1; n],
            siz: vec![1; n],
        }
    }

    // 根を求める
    pub fn root(&mut self, x: usize) -> usize {
        if self.par[x] == -1 {
            return x; // x が根の場合は x を返す
        } else {
            self.par[x] = self.root(self.par[x] as usize) as i64;
            return self.par[x] as usize;
        }
    }

    // x と y が同じグループに属するかどうか (根が一致するかどうか)
    pub fn issame(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    // x を含むグループと y を含むグループとを併合する
    pub fn unite(&mut self, x: usize, y: usize) -> bool {
        // x, y をそれぞれ根まで移動する
        let mut x = self.root(x);
        let mut y = self.root(y);

        // すでに同じグループのときは何もしない
        if x == y {
            return false;
        }

        // union by size (y 側のサイズが小さくなるようにする)
        if self.siz[x] < self.siz[y] {
            // swap(x, y);
            let tmp = y;
            y = x;
            x = tmp;
        }

        // y を x の子とする
        self.par[y] = x as i64;
        self.siz[x] += self.siz[y];
        return true;
    }

    // x を含むグループのサイズ
    pub fn size(&mut self, x: usize) -> u64 {
        let r = self.root(x);
        return self.siz[r as usize];
    }
}

fn main() {
  input!{
  n:usize,
  m:usize,
  ab:[[usize;2];m]
  }
  let mut uf = UnionFind::new(n);
  for i in ab{
    uf.unite(i[0]-1, i[1]-1);
  }
//root,size,issame 括弧数字は+1すると元の数字、セミコロンの右コメントが出力
println!("{}",uf.root(1)+1);//1
println!("{}",uf.size(1));//3

println!("{}",uf.root(3)+1);//3
println!("{}",uf.size(3));//2

println!("{}",uf.root(4)+1);//1
println!("{}",uf.size(4));//3
println!("{}",uf.issame(1,4));//true

}