Find the Connected Component in the Undirected Graph
Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)
http://www.lintcode.com/en/problem/find-the-connected-component-in-the-undirected-graph/
Solution
就是BFS,没啥好说的。
class Solution {
public:
/**
* @param nodes a array of Undirected graph node
* @return a connected set of a Undirected graph
*/
vector<vector<int>> connectedSet(vector<UndirectedGraphNode*>& nodes) {
// Write your code here
vector<vector<int> > result;
unordered_set<UndirectedGraphNode*> is_visited;
vector<int> component;
for(auto const& node : nodes) {
if(is_visited.find(node) == is_visited.end()) {
bsf(node, is_visited, component);
sort(component.begin(), component.end());
result.emplace_back(component);
component.clear();
}
}
return result;
}
void bsf(UndirectedGraphNode* node, unordered_set<UndirectedGraphNode*> &is_visited,
vector<int> &records) {
queue<UndirectedGraphNode*> myque;
myque.emplace(node);
is_visited.emplace(node);
while(!myque.empty()) {
UndirectedGraphNode *cur = myque.front();
myque.pop();
records.emplace_back(cur->label);
for(auto const& n : cur->neighbors) {
if(is_visited.find(n) == is_visited.end()) {
is_visited.emplace(n);
myque.emplace(n);
}
}
}
}
};