547. 省份数量(leetcode)
https://leetcode.cn/problems/number-of-provinces/
并查集模版题
class Solution {
int[] p;
void init(int n)
{
p=new int[n];
for(int i=0;i<n;i++)p[i]=i;
}
int find(int x)
{
return x==p[x] ? x:(p[x]=find(p[x]));
}
void union(int x,int y)
{
p[find(x)]=find(y);
}
public int findCircleNum(int[][] isConnected) {
int res=0;
init(isConnected.length);
for(int i=0;i<isConnected.length;i++)
for(int j=0;j<isConnected[i].length;j++)
{
if(isConnected[i][j]==1)union(i,j);
}
// 查询并查集数量
for(int i=0;i<isConnected.length;i++)
{
if(find(i)==i)res++;
}
return res;
}
}