Find the Connected Component in the Undirected Graph (Ladder)

Description

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

Notice
Each connected component should sort by label.

Clarification Learn more about representation of graphs

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}

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * Definition for Undirected graph.
   * struct UndirectedGraphNode {
   *     int label;
   *     vector<UndirectedGraphNode *> neighbors;
   *     UndirectedGraphNode(int x) : label(x) {};
   * };
   */
   class Solution {
   public:
    /**
     * @param nodes a array of Undirected graph node
     * @return a connected set of a Undirected graph
     */
    vector<vector<int>> connectedSet(vector<UndirectedGraphNode*>& nodes) {
        // Write your code here
        vector<vector<int>> result;
        if (nodes.empty()) {
           return result; 
        }
        int len = nodes.size();
        queue<UndirectedGraphNode*> q;
        vector<int> row;
        unordered_set<UndirectedGraphNode*> used;
        // Try every entry to find connect
        for (int i = 0; i < len; ++i) {
            // valid pointer
            if (!nodes[i]) {
                continue;
            }
            // de-dup
            if (used.find(nodes[i]) != used.end()) {
                continue;
            }
            // bfs get group
            row = bfs(nodes[i], used);
            sort(row.begin(), row.end());
            result.push_back(row);
        }
        return result;
    }
    // bfs
    // if we find any part of a group, we can reach every entry of the group
    // So, duplicate will be avoided
    vector<int> bfs(UndirectedGraphNode* head, 
        unordered_set<UndirectedGraphNode*>& used
    ){
        vector<int> result;
        queue<UndirectedGraphNode*> q;
        q.push(head);
        used.insert(head);
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            result.push_back(cur->label);
            for (const auto& i : cur->neighbors ) {
                if (used.find(i) != used.end()) {
                    continue;
                }
                q.push(i);
                used.insert(i);
            }
        }
        return result;
    }
   };
   

Similar problems

x

Tags

x