forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
clone-graph.py
27 lines (23 loc) · 848 Bytes
/
clone-graph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Time: O(n)
# Space: O(n)
class UndirectedGraphNode(object):
def __init__(self, x):
self.label = x
self.neighbors = []
class Solution(object):
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if node is None:
return None
cloned_node = UndirectedGraphNode(node.label)
cloned, queue = {node:cloned_node}, [node]
while queue:
current = queue.pop()
for neighbor in current.neighbors:
if neighbor not in cloned:
queue.append(neighbor)
cloned_neighbor = UndirectedGraphNode(neighbor.label)
cloned[neighbor] = cloned_neighbor
cloned[current].neighbors.append(cloned[neighbor])
return cloned[node]