17. UnionFind

• 算法介紹: https://blog.csdn.net/dm_vincent/article/details/7655764

• 合併集合

• 判斷元素是否在同一個集合中

public class unionFind{
    // 紀錄上一層的node
    private int[] father = null;
    // 記錄有幾個組
    private int count;
    // 記錄每組有幾個元素
    private int[] size = null;
    // initiate data structure
    public unionFind(int n){
        count = n;
        father = new int[n];
        size = new int[n];
        for(int i=0; i<n; i++){
            father[i] = i;
            size[i] = 1;
        }
    }
    // path compression
    private find(int x){
        if(father[x] != x) father[x] = find(father[x]);
        return father[x];
    }

    public void union(int p, int q){
        int root_p = find(p);
        int root_q = find(q);
        if(root_p == root_q) return;
        if(size(root_p) > size(root_q)){
            father[root_q] = root_p;
            size[root_p] += size[root_q];

        } 
        else{
            father[root_p] = root_q; 
            size[root_q] += size[root_p];
        }
        count--; 
    }