Connected Component in 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}

Solution:

求解决方案的具体个数可以想到DFS, 但是隐式DFS的模式大多都是在循环内把结果添加进入临时的current变量， 但是对于图不是特别适合，主要是图有邻居节点，简单的做法就是在利用isVisited 字典，只访问节点一次，第二添加结果集在DFS循环外。这道题的第二个重点就是，结果返回的label集合，而不是节点集合。

# 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
        isVisited = {}
        for node in nodes:
            isVisited[node.label] = False
        result = []
        for node in nodes:
            if not isVisited[node.label]:
                current = []
                self.DFS(isVisited, node, current)
                result.append(sorted(current))
        return result

    def DFS(self, isVisited, node, current):
        isVisited[node.label] = True
        current.append(node.label)
        for neighbor in node.neighbors:
            if not isVisited[neighbor.label]:
                self.DFS(isVisited, neighbor, current)