力扣原题链接:省份数量
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnectedi = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnectedi = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1:
输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2
示例 2:
输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3
提示:
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnectedi 为 1 或 0
isConnectedi == 1
isConnectedi == isConnectedj
package com.harrison.class10;
/**
* @author Harrison
* @create 2022-03-19-13:11
* @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
*/
public class Code02_FriendCircles {
// https://leetcode.com/problems/friend-circles/
public static class UnionFind{
// parent[i]=k i的父亲是K
public int[] parent;
// size[i]=k 如果i是代表结点,size[i]才有意义,否则无意义
// i所在的集合大小是k
public int[] size;
// 辅助结构
public int[] help;
// 一共有多少个集合
public int sets;
public UnionFind(int N){
parent=new int[N];
size=new int[N];
help=new int[N];
sets=N;
for(int i=0; i<N; i++){
parent[i]=i;
size[i]=i;
}
}
// 从i开始往上,往上到不能再往上,就是代表结点,返回
// 这个过程要做路径压缩
public int find(int i){
int hi=0;
while (i!=parent[i]){
help[hi++]=i;
i=parent[i];
}
for(hi--; hi>=0; hi--){
parent[help[hi]]=i;
}
return i;
}
public void union(int i,int j){
int f1=find(i);
int f2=find(j);
if(f1!=f2){
if(size[f1]>=size[f2]){
size[f1]+=size[f2];
parent[f2]=f1;
}else{
size[f2]+=size[f1];
parent[f1]=f2;
}
sets--;
}
}
public int sets(){
return sets;
}
}
public static int findCircleNum(int[][] isConnected){
int N=isConnected.length;
// {0} {1} {2} {3}...{N-1}
UnionFind unionFind=new UnionFind(N);
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
if(isConnected[i][j]==1){// i和j互相认识
unionFind.union(i,j);
}
}
}
return unionFind.sets;
}
}