參考文章：http://www.itdecent.cn/p/89cea54d3f22

并查集介紹

并查集，在一些有N個元素的集合應(yīng)用問題中，我們通常是在開始時讓每個元素構(gòu)成一個單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個元素在哪個集合中。
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢問題。

主要操作：初始化、查找、合并
下面是我的代碼：

//并查集實現(xiàn)
public class bingchajiDemo {
    static int[] par = new int[6]; // 父親
    static int[] rank = new int[6]; //樹的高度

    // 初始化n個元素
    public static void init(int n){
        for(int i=1 ; i <= n ; i++){
            par[i] = i;
            rank[0] = 0;
        }
    }

    // 查詢樹的根
    public static int find(int x){
        if(par[x] == x){
            return x;
        }else{
            par[x] = find(par[x]);
            return par[x];
        }
    }

    //合并x和y所屬的集合
    public static void unite(int x,int y){
        x = find(x);
        y = find(y);
        if(x == y){
            return;
        }
        if (rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]){
                rank[x] ++;
            }
        }
    }

    //判斷x y是不是在同一個集合
    public static boolean  same(int x, int y){
        return find(x) == find(y);
    }

    public static void main(String[] args) {
        init(5);
        System.out.println(find(2));
    }

}

算法訓(xùn)練

https://www.cnblogs.com/attacking-vincent/p/13154731.html
食物鏈

//并查集實現(xiàn)
public class bingchajiDemo {
    static int[] par = new int[3*150010]; // 父親
    static int[] rank = new int[3*150010]; //樹的高度

    // 初始化n個元素
    public static void init(int n){
        for(int i=1 ; i <= n ; i++){
            par[i] = i;
            rank[0] = 0;
        }
    }

    // 查詢樹的根
    public static int find(int x){
        if(par[x] == x){
            return x;
        }else{
            par[x] = find(par[x]);
            return par[x];
        }
    }

    //合并x和y所屬的集合
    public static void unite(int x,int y){
        x = find(x);
        y = find(y);
        if(x == y){
            return;
        }
        if (rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]){
                rank[x] ++;
            }
        }
    }

    //判斷x y是不是在同一個集合
    public static boolean  same(int x, int y){
        return find(x) == find(y);
    }

    // 解決
    public static void solve(int n,int k,int[] T,int[] X,int[] Y){
        init(n*3);
        int ans = 0;
        for (int i=0 ;i<k ;i++){
            int t = T[i];
            int x = X[i]-1;
            int y = Y[i]-1;
            // 不正確編號
            if(x<0||n<=x||y<0||n<=y){
                ans++;
                continue;
            }

            if(t==1){
                if(same(x,y+n)||same(x,y+2*n)){
                    ans ++;
                }else{
                    unite(x,y);
                    unite(x+n,y+n);
                    unite(x+2*n,y+2*n);
                }
            }else{
                if(same(x,y)||same(x,y+2*n)){
                    ans++;
                }else{
                    unite(x,y+n);
                    unite(x+n,y+2*n);
                    unite(x+2*n,y);
                }
            }

        }

        System.out.println("ans:"+ans);

    }

    public static void main(String[] args) {
        int n = 100;
        int k = 7;
        int[] T = {1,2,2,2,1,2,1};
        int[] X = {101,1,2,3,1,3,5};
        int[] Y = {1,2,3,3,3,1,5};
        solve(n,k,T,X,Y);

    }
}