[LintCode] Find the Connected Component in the Undirected Graph

雨点打透心脏的1/2处 2022-03-29 06:45 140阅读 0赞

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

**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}`

DFS:

1 /**
     2  * Definition for Undirected graph.
     3  * struct UndirectedGraphNode {
     4  *     int label;
     5  *     vector<UndirectedGraphNode *> neighbors;
     6  *     UndirectedGraphNode(int x) : label(x) {};
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     /**
    12      * @param nodes a array of Undirected graph node
    13      * @return a connected set of a Undirected graph
    14      */
    15     void dfs(vector<UndirectedGraphNode*> &nodes, vector<int> &path,
    16             unordered_set<UndirectedGraphNode*> &visit, UndirectedGraphNode* n) {
    17         visit.insert(n);
    18         path.push_back(n->label);
    19         for (auto &nn : n->neighbors) if (visit.find(nn) == visit.end()) {
    20             dfs(nodes, path, visit, nn);
    21         }
    22     }
    23     vector<vector<int>> connectedSet(vector<UndirectedGraphNode*>& nodes) {
    24         // Write your code here
    25         unordered_set<UndirectedGraphNode*> visit;
    26         vector<vector<int>> res;
    27         vector<int> path;
    28         for (auto &n : nodes) {
    29             if (visit.find(n) == visit.end()) {
    30                 path.clear();
    31                 dfs(nodes, path, visit, n);
    32                 sort(path.begin(), path.end());
    33                 res.push_back(path);
    34             } 
    35         }
    36         return res;
    37     }
    38 };

BFS:

1 /**
     2  * Definition for Undirected graph.
     3  * struct UndirectedGraphNode {
     4  *     int label;
     5  *     vector<UndirectedGraphNode *> neighbors;
     6  *     UndirectedGraphNode(int x) : label(x) {};
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     /**
    12      * @param nodes a array of Undirected graph node
    13      * @return a connected set of a Undirected graph
    14      */
    15     vector<vector<int>> connectedSet(vector<UndirectedGraphNode*>& nodes) {
    16         // Write your code here
    17         unordered_set<UndirectedGraphNode*> visit;
    18         vector<vector<int>> res;
    19         vector<int> path;
    20         queue<UndirectedGraphNode*> que;
    21         for (auto &n : nodes) {
    22             if (visit.find(n) == visit.end()) {
    23                 path.clear();
    24                 visit.insert(n);
    25                 for (que.push(n); !que.empty(); que.pop()) {
    26                     auto u = que.front();
    27                     path.push_back(u->label);
    28                     for (auto nn : u->neighbors) if (visit.find(nn) == visit.end()) {
    29                         visit.insert(nn);
    30                         que.push(nn);
    31                     }
    32                 }
    33                 sort(path.begin(), path.end());
    34                 res.push_back(path);
    35             } 
    36         }
    37         return res;
    38     }
    39 };

[Find the Connected Component in the Undirected Graph]: http://www.lintcode.com/en/problem/find-the-connected-component-in-the-undirected-graph/