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.)
Notice
Each connected component should sort by label.
Have you met this question in a real interview?
Yes
Clarification
Learn more about representation of graphs
Example
Given graph:
A------B C
\ | |
\ | |
\ | |
\ | |
D E
Return{A,B,D}, {C,E}
. Since there are two connected component which is{A,B,D}, {C,E}
bfs, only add node once to queue
/**
* Definition for Undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
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>> res;
Initialize(nodes);
unordered_map<UndirectedGraphNode*, vector<int>> sets;
for (auto& node : nodes) {
for (auto& next : node->neighbors) {
Union(node, next);
}
}
for (auto& node : nodes) {
sets[FindParent(node)].push_back(node->label);
}
for (auto nodes : sets) {
auto& it = nodes.second;
sort(it.begin(), it.end());
res.push_back(it);
}
return res;
}
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
void Initialize(vector<UndirectedGraphNode*>& nodes) {
for (auto& node : nodes) {
mp[node] = node;
}
}
UndirectedGraphNode* FindParent(UndirectedGraphNode* node) {
while (node != mp[node]) {
node = mp[node];
}
return node;
}
void Union(UndirectedGraphNode* left, UndirectedGraphNode* right) {
UndirectedGraphNode* pLeft = FindParent(left);
UndirectedGraphNode* pRight = FindParent(right);
if (pLeft != pRight) {
mp[pRight] = pLeft;
}
}
};