Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.)
Notice
Sort the element in the set in increasing order
Have you met this question in a real interview?
Yes
Example
Given graph:
A-----
>
B C
\ | |
\ | |
\ | |
\ v v
-
>
D E
<
- F
Return{A,B,D}, {C,E,F}
. Since there are two connected component which are{A,B,D} and {C,E,F}
/**
* Definition for Directed graph.
* struct DirectedGraphNode {
* int label;
* vector<DirectedGraphNode *> neighbors;
* DirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
/**
* @param nodes a array of directed graph node
* @return a connected set of a directed graph
*/
vector<vector<int>> connectedSet2(vector<DirectedGraphNode>& nodes) {
// Write your code here
vector<vector<int>> res;
Initialize(nodes);
unordered_map<DirectedGraphNode*, 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<DirectedGraphNode*, DirectedGraphNode> mp;
void Initialize(vector<DirectedGraphNode>& nodes) {
for (auto& node : nodes) {
mp[node] = node;
}
}
DirectedGraphNode* FindParent(DirectedGraphNode* node) {
while (node != mp[node]) {
node = mp[node];
}
return node;
}
void Union(DirectedGraphNode* left, DirectedGraphNode* right) {
DirectedGraphNode* pLeft = FindParent(left);
DirectedGraphNode* pRight = FindParent(right);
if (pLeft != pRight) {
mp[pRight] = pLeft;
}
}
};