建设银行东航龙卡登录东航网站,响应式视频网站模板下载,wordpress主题简约,衡水网站联系电话假设#xff1a;有一群小混混打架#xff0c;小弟们可能互相不认识#xff0c;如果要确定他们是一伙的#xff0c;就需要确定他们的组长是不是一个#xff0c;但是每个组长的领导可能又不一样#xff0c;所以要找到最大的那个领导#xff0c;才能确定是一伙的。
我们先…假设有一群小混混打架小弟们可能互相不认识如果要确定他们是一伙的就需要确定他们的组长是不是一个但是每个组长的领导可能又不一样所以要找到最大的那个领导才能确定是一伙的。
我们先初始化一个数组用来存储每个成员的领导初始化每个成员的领导就是他自己。 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){//如果当前元素不是最高级继续去找它上级的上级xpre[x];}return x;}
但是可能存在着这样的关系A的领导是BB的领导是CC的领导是D。甲的领导是乙乙的领导是丙丙的领导是丁。这样就意味着存在两个组织。但是丙又成为了B的领导所以这两个资质就需要进行合并成为一个组织。
对应以下代码 //合并void merge(int x,int y,int pre[]){int afind(x,pre);int bfind(y,pre);pre[a]b;}
力扣链接547. 省份数量 - 力扣LeetCode
class Solution {//查找元素的最高上级int find(int x,int [] pre){//因为初始化的时候我们将所有元素的最高级设为自己//所以最高级是自己的元素即为最高级元素while (pre[x]!x){//如果当前元素不是最高级继续去找它上级的上级xpre[x];}return x;}//合并void merge(int x,int y,int pre[]){int afind(x,pre);int bfind(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 count0;for (int i 0; i pre.length; i) {if(pre[i]i){count;}}return count;}
}
