Find the Connected Component in the Undirected Graph

Question

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}

Thoughts

用一个hashmap保存visit过的点 对每一个点做bfs

Solution

from collections import deque
# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    # @param {UndirectedGraphNode[]} nodes a array of undirected graph node
    # @return {int[][]} a connected set of a undirected graph
    def connectedSet(self, nodes):
        # Write your code here
        self.visited = {}
        self.result = []

        for node in nodes:
            if node not in self.visited:
                self.bfs(node)

        return self.result

    def bfs(self, node):
        subG = []
        queue = deque()

        self.visited[node] = True
        queue.append(node)
        while queue:
            cur = queue.popleft()
            subG.append(cur.label)

            for neighbor in cur.neighbors:
                if neighbor not in self.visited:
                    self.visited[neighbor] = True
                    queue.append(neighbor)

        #no sort no correct
        subG.sort()
        self.result.append(subG)