323. Number of Connected Components in an Undirected Graph

本文主要是介绍323. Number of Connected Components in an Undirected Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

寻找多少个独立的图，那不就是遍历完一个图，然后遍历其他图吗？直到所有的点都遍历完。
创建两个unordered_set，一个记录访问过的，一个记录没有访问过的点。
遍历每个图的节点的时候，动态的更新这两个set。

当第一个独立的图遍历完后 ret++；

如果记录没有访问过的点不为空，那么就继续循环去遍历。

这个办法可以，但是效率低。

class Solution {
public:
unordered_map<int, vector<int>> buildGraph(vector<vector<int>> edges) {
unordered_map<int, vector<int>> graph;

for(auto & edge: edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
return graph;
}


int countComponents(int n, vector<vector<int>>& edges) {
//寻找多少个独立的图，那不就是遍历完一个图，然后遍历其他图吗？直到所有的点都遍历完。
//创建两个unordered_set，一个记录访问过的，一个记录没有访问过的点。
//遍历每个图的节点的时候，动态的更新这两个set。

if(edges.size() == 0 && n == 1)
return 1;
else if(edges.size() == 0 && n == 0)
return 0;

int ret;

queue<int> myqueue;
unordered_set<int> accessedVertex, unAccessedVertex;

for(int i=0;i<n;i++)
unAccessedVertex.insert(i);

unordered_map<int, vector<int>> neighbors = buildGraph(edges);

while(unAccessedVertex.size()!=0) {
int tmp = *unAccessedVertex.begin();
myqueue.push(tmp);
accessedVertex.insert(tmp);
unAccessedVertex.erase(tmp);

while(!myqueue.empty()) {
int v = myqueue.front();
myqueue.pop();

for(auto &neighbor: neighbors[v]) {
if(accessedVertex.find(neighbor) != accessedVertex.end())
continue;
else
{ myqueue.push(neighbor);
accessedVertex.insert(neighbor);
unAccessedVertex.erase(neighbor);
}
}
}
ret++;
}

return ret;
}
};