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
       
         neighbors; 6  *     UndirectedGraphNode(int x) : label(x) {}; 7  * }; 8  */ 9 class Solution {10 public:11     /**12      * @param nodes a array of Undirected graph node13      * @return a connected set of a Undirected graph14      */15     void dfs(vector
        
          &nodes, vector
         
           &path,16             unordered_set
          
            &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
           
            
             > connectedSet(vector
             
              & nodes) {24 // Write your code here25 unordered_set
              
                visit;26 vector
               
                
                 > res;27 vector
                 
                   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
       
         neighbors; 6  *     UndirectedGraphNode(int x) : label(x) {}; 7  * }; 8  */ 9 class Solution {10 public:11     /**12      * @param nodes a array of Undirected graph node13      * @return a connected set of a Undirected graph14      */15     vector
        
         
          > connectedSet(vector
          
           & nodes) {16         // Write your code here17         unordered_set
           
             visit;18         vector
            
             
              > res;19 vector
              
                path;20 queue
               
                 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 };