"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
BFS
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
#!!!! the key point to solving the problem is to avoid circle when doing graph traverse
# time O(N+E)E: edges space O(N)
if not node:
return node
q = collections.deque()
q.append(node)
d = {node:Node(node.val)}
while q:
no = q.popleft()
for nei in no.neighbors:
# case1: nei not in d --> (1)put nei in queue (2) create new nei; (3)add new nei in d (4) put new nei as copy no's neighbour
# case2: nei in the d --> means copy nei exists (1) put copy nei as copy no's neighbour
if nei not in d:
q.append(nei)
# !!!! reuse nei_copy is critial
nei_copy = Node(nei.val)
d[nei] = nei_copy
d[no].neighbors.append(nei_copy)
else:
d[no].neighbors.append(d[nei])
return d[node]
DFS solution
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
# time O(V+E) space O(V+E)
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return node
d = {node:Node(node.val)}
st = [node]
while st:
no = st.pop()
for nei in no.neighbors:
if nei not in d:
copy_nei = Node(nei.val)
d[nei] = copy_nei
d[no].neighbors.append(copy_nei)
st.append(nei)
else:
# means copy no has not connected with copy nei
d[no].neighbors.append(d[nei])
return d[node]