"Clone Graph" asks you to deep-copy an undirected graph given one node. The real test is whether you notice that graphs can contain cycles, so a naive recursive copy will loop forever.
Keep a dictionary old_to_new. Before creating a copy of a node, check whether it already exists in the map. This single structure does two jobs: it is your visited set, and it lets you wire up neighbors to the correct copies.
def clone_graph(node):
if node is None:
return None
old_to_new = {}
def dfs(cur):
if cur in old_to_new:
return old_to_new[cur]
copy = Node(cur.val)
old_to_new[cur] = copy # register BEFORE visiting neighbors
for nb in cur.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)
Point out why you register the copy before recursing: if you waited until after, a cycle such as 1-2-1 would create a second copy of node 1.
from collections import deque
def clone_graph_bfs(node):
if not node:
return None
old_to_new = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nb in cur.neighbors:
if nb not in old_to_new:
old_to_new[nb] = Node(nb.val)
q.append(nb)
old_to_new[cur].neighbors.append(old_to_new[nb])
return old_to_new[node]
Want help staying calm and structured during live coding rounds? this tool from Linkjob AI gives real-time hints during coding interviews.
Disclosure: written by the Linkjob AI team.