原题
找出无向图中所有的连通块。
图中的每个节点包含一个label属性和一个邻接点的列表。（一个无向图的�连通块是一个子图，其中任意两个顶点通过路径相连，且不与整个图中的其它顶点相连。）
样例
给定图:
A------B C
\ | |
\ | |
\ | |
\ | |
D E
返回 {A,B,D}, {C,E}。其中有 2 个连通块，即{A,B,D}, {C,E}
解题思路
方法一：对于无向图，首先要建立一个hash map来去重，然后遍历每一个节点，若该节点不在hash map中，则通过DFS找到所有相连的节点
方法二：Union Find
本题也可以使用并查集(Union Find)来解决，虽然不是最适合Union Find的题目。在有向图中寻找连通块才是Union Find的用武之地。更多关于Union Find的知识点，详见Find the Weak Connected Component in the Directed Graph
完整代码
# Method 1
# 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.hashMap = {}
for node in nodes:
self.hashMap[node.label] = False
res = []
for node in nodes:
if not self.hashMap[node.label]:
temp = []
self.dfs(node, temp)
res.append(sorted(temp))
return res
def dfs(self, node, temp):
self.hashMap[node.label] = True
temp.append(node.label)
for neighbor in node.neighbors:
if not self.hashMap[neighbor.label]:
self.dfs(neighbor, temp)
