参考文章：https://www.jianshu.com/p/89cea54d3f22

并查集介绍

并查集，在一些有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));
    }

}

算法训练

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

//并查集实现
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);

    }
}