并查集---力扣547省份的数量

假设：有一群小混混打架，小弟们可能互相不认识，如果要确定他们是一伙的，就需要确定他们的组长是不是一个，但是每个组长的领导可能又不一样，所以要找到最大的那个领导，才能确定是一伙的。

我们先初始化一个数组，用来存储每个成员的领导，初始化每个成员的领导就是他自己。

   void init(int[] pre) {
        for (int i = 0; i < pre.length; i++) {
            pre[i]=i;
        }
    }

通过find方法来寻找每位成员的直属领导

  //查找元素的最高上级
     int find(int x,int [] pre){
        //因为初始化的时候，我们将所有元素的最高级设为自己
        //所以最高级是自己的元素即为最高级元素
        while (pre[x]!=x){
        //如果当前元素不是最高级，继续去找它上级的上级
            x=pre[x];
        }
        return x;
    }

但是可能存在着这样的关系，A的领导是B，B的领导是C，C的领导是D。甲的领导是乙，乙的领导是丙，丙的领导是丁。这样就意味着存在两个组织。但是丙又成为了B的领导，所以这两个资质就需要进行合并成为一个组织。

对应以下代码

 //合并
    void merge(int x,int y,int pre[]){
        int a=find(x,pre);
        int b=find(y,pre);
        pre[a]=b;
    }

力扣链接：547. 省份数量 - 力扣（LeetCode）

class Solution {
     //查找元素的最高上级
     int find(int x,int [] pre){
        //因为初始化的时候，我们将所有元素的最高级设为自己
        //所以最高级是自己的元素即为最高级元素
        while (pre[x]!=x){
        //如果当前元素不是最高级，继续去找它上级的上级
            x=pre[x];
        }
        return x;
    }

    //合并
    void merge(int x,int y,int pre[]){
        int a=find(x,pre);
        int b=find(y,pre);
        pre[a]=b;
    }

     //初始化最高级数组，数组意思是记录当前元素的直接上级
      void init(int[] pre) {
        for (int i = 0; i < pre.length; i++) {
            pre[i]=i;
        }
    }
    public int findCircleNum(int[][] isConnected) {
        int pre[] = new int[isConnected.length];//元素的数量
        init(pre);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                if(i!=j){
                    if(isConnected[i][j]==1){
                        merge(i,j,pre);
                    }
                }
            }
        }
        int count=0;
        for (int i = 0; i < pre.length; i++) {
            if(pre[i]==i){
                count++;
            }
        }
        return count;
    }
}