class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if node is None:
return
hs = {}
que = [node]
while que:
nd = que.pop(0)
if not hs.has_key(nd.label):
res1 = UndirectedGraphNode(nd.label)
hs[nd.label] = res1
else:
res1 = hs[nd.label]
for i in nd.neighbors:
if not hs.has_key(i.label):
que.append(i)
temp = UndirectedGraphNode(i.label)
hs[temp.label] = temp
res1.neighbors.append(temp)
else:
res1.neighbors.append(hs[i.label])
return hs[node.label]
Python solution with BFS, 120ms


Good solution, it seems better to use deque instead of queue (list) in this case:
def cloneGraph(self, node): if not node: return None dic, queue = dict(), collections.deque([node]) while queue: curr = queue.popleft() if curr.label not in dic: newNode = UndirectedGraphNode(curr.label) dic[curr.label] = newNode else: newNode = dic[curr.label] for neighbor in curr.neighbors: if neighbor.label not in dic: queue.append(neighbor) tmp = UndirectedGraphNode(neighbor.label) dic[tmp.label] = tmp newNode.neighbors.append(tmp) else: newNode.neighbors.append(dic[neighbor.label]) return dic[node.label]