LeetCode 547. 【并查集】省份数量
原题链接
简单
作者:
大明湖的鱼
,
2021-01-07 20:10:22
,
所有人可见
,
阅读 388
裸的并查集,一遍过
class Solution {
public:
int find(vector<int>& p, int x){
if(p[x] != x) p[x] = find(p,p[x]);
return p[x];
}
void merge(vector<int>& p,int a,int b){
int pa = find(p,a);
int pb = find(p,b);
p[pa] = pb;
}
int findCircleNum(vector<vector<int>>& isConnected) {
vector<int> p(isConnected.size());
for(int i = 0 ;i < isConnected.size(); i++){
p[i] = i;
}
for(int i=0;i<isConnected.size();i++){
for(int j=i+1;j<isConnected.size();j++){
if(isConnected[i][j])merge(p,i,j);
}
}
int res = 0;
for(int i=0;i<isConnected.size();i++){
if(p[i] == i) res++;
}
return res;
}
};