Number of Connected Components in an Undirected Graph
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.
Example 1:
0 3
| |
1 --- 2 4Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.
Example 2:
0 4
| |
1 --- 2 --- 3Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.
分析：
类似于图像处理中找到物体轮廓的泛洪算法。在本题中，每个点扫一遍，每条边扫一遍，点和边都不重复遍历，复杂度为O(V + E)
代码：
int number(int n, vector<pair<int, int> > edges) {
//Store edges with hash map for efficient access
unordered_multimap<int, int> hash;
for(auto e : edges) {
hash.insert(e);
hash.insert(make_pair(e.second, e.first));
}
//Flood fill algorithm
vector<bool> visited(n, false);
int number = ;
for(int i = ; i < n; i++) {
if(!visited[i]) {
number++;
visited[i] = true;
queue<int> myq;
myq.push(i);
while(!myq.empty()) {
auto range = hash.equal_range(myq.front());
myq.pop();
auto pos = range.first;
while(pos != range.second) {
if(!visited[pos->second]) {
myq.push(pos->second);
visited[pos->second] = true;
}
pos++;
}
}
}
}
return number;
}