Find the Weak Connected Component in the Directed Graph

Description:

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.)

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}

Solution:

( Union-Find Sets )

/** * Definition for Directed graph. * struct DirectedGraphNode { * int label; * vector<DirectedGraphNode *> neighbors; * DirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { private: unordered_map<DirectedGraphNode*, DirectedGraphNode*> cache; DirectedGraphNode* find(DirectedGraphNode* node) { if (cache[node] != node) cache[node] = find(cache[node]); return cache[node]; } void merge(DirectedGraphNode* n1, DirectedGraphNode* n2) { auto f1 = find(n1); auto f2 = find(n2); if (f1 != f2) cache[f2] = f1; } public: /** * @param nodes a array of directed graph node * @return a connected set of a directed graph */ vector<vector<int>> connectedSet2(vector<DirectedGraphNode*>& nodes) { vector<vector<int>> rc; for (auto& node : nodes) cache[node] = node; for (auto& node : nodes) for (auto& ngb : node->neighbors) merge(node, ngb); unordered_map<DirectedGraphNode*, int> index; for (auto& node : nodes) { auto father = find(node); if (index.find(father) == index.end()) { rc.push_back(vector<int>({node->label})); index[father] = rc.size()-1; } else rc[index[father]].push_back(node->label); } return rc; } };

转载于:https://www.cnblogs.com/deofly/p/ind-the-weak-connected-component-in-the-directed-graph.html

相关资源：JAVA上百实例源码以及开源项目