LeetCode刷题实战323:无向图中连通分量的数目
共 2902字,需浏览 6分钟
·
2021-07-18 11:19
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
示例
解题
class Solution {
public:
//找每一个顶点的老大
int find_father(vector<int> &f, int i){
while(i!=f[i]){
i=f[i];
}
return i;
}
int countComponents(int n, vector<vector<int>>& edges) {
vector<int>f(n);
//将每一个顶点单独分成一组
for(int i=0; i<n; ++i){
f[i]=i;
}
//进行同一组的顶点的合并
for(auto x:edges){
int p=find_father(f, x[0]);
int q=find_father(f, x[1]);
if(p==q) continue;
else f[p]=q;
}
//找一共有多少个不同的老大
unordered_set<int>s;
for(int i=0; i<f.size(); ++i){
s.insert(find_father(f, i));
}
return s.size();
}
};