原題
找出無向圖中所有的連通塊缔御。
圖中的每個(gè)節(jié)點(diǎn)包含一個(gè)label屬性和一個(gè)鄰接點(diǎn)的列表。（一個(gè)無向圖的?連通塊是一個(gè)子圖挣棕，其中任意兩個(gè)頂點(diǎn)通過路徑相連驮樊，且不與整個(gè)圖中的其它頂點(diǎn)相連。）
樣例
給定圖:
A------B C
\ | |
\ | |
\ | |
\ | |
D E
返回 {A,B,D}, {C,E}拟逮。其中有 2 個(gè)連通塊撬统，即{A,B,D}, {C,E}
解題思路
方法一：對于無向圖，首先要建立一個(gè)hash map來去重敦迄，然后遍歷每一個(gè)節(jié)點(diǎn)恋追，若該節(jié)點(diǎn)不在hash map中，則通過DFS找到所有相連的節(jié)點(diǎn)
方法二：Union Find
本題也可以使用并查集(Union Find)來解決罚屋，雖然不是最適合Union Find的題目苦囱。在有向圖中尋找連通塊才是Union Find的用武之地。更多關(guān)于Union Find的知識點(diǎn)脾猛，詳見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)
