Connected Component in Undirected Graph

• Lintcode : 431 / Leetcode : 323
• Level : Medium

Problem

Find connected component in undirected graph.

Each node in the graph contains a label and a list of its neighbors.

(A connected 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.)

You need return a list of label set.

Example
Example 1:

Input: {1,2,4#2,1,4#3,5#4,1,2#5,3}
Output: [[1,2,4],[3,5]]
Explanation:

  1------2  3
   \     |  | 
    \    |  |
     \   |  |
      \  |  |
        4   5
Example 2:

Input: {1,2#2,1}
Output: [[1,2]]
Explanation:

  1--2

Clarification
Learn more about representation of graphs

Notice
Nodes in a connected component should sort by label in ascending order. Different connected components can be in any order.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

/**
 * Definition for Undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
    vector<vector<int>> connectedSet(vector<UndirectedGraphNode*> nodes) {
        set<UndirectedGraphNode*> repeat;
        vector<vector<int>> ans;
        for (auto n : nodes) {
            if (repeat.find(n) != repeat.end()) continue;
            bfs (n, repeat, ans);
        }
        return ans;
    }

    void bfs (UndirectedGraphNode* n, set<UndirectedGraphNode*> &repeat, vector<vector<int>> &ans) {
        if (n == nullptr) return;
        vector<int> res;
        queue<UndirectedGraphNode*> q;
        q.push(n);
        repeat.insert(n);
        while (!q.empty()) {
            UndirectedGraphNode* node = q.front(); q.pop();
            res.push_back(node -> label);
            for (auto neighbor : node -> neighbors) {
                if (repeat.find(neighbor) != repeat.end()) continue;
                q.push(neighbor);
                repeat.insert(neighbor);
            }
        }
        sort(res.begin(), res.end());
        ans.push_back(res);
    }
};

tags: BFS

​