114百事通做网站600手机百度官网

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

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

   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;}
}