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;

}

}
};

results matching ""

    No results matching ""