The tell: Deep-copy a structure containing cycles, so naive recursion would loop forever.
How you get there
1Keep a map from original node to its copy.
2Check the map before recursing — that both terminates cycles and de-duplicates.
3Create the copy before recursing into neighbours, or a cycle re-enters before the entry exists.
Solution
Python
def clone_graph(node):
if not node:
return None
copies: dict = {}
def dfs(current):
if current in copies:
return copies[current]
clone = Node(current.val)
copies[current] = clone # register before recursing
for neighbour in current.neighbors:
clone.neighbors.append(dfs(neighbour))
return clone
return dfs(node)
Time
O(V + E)
Space
O(V)
What goes wrong
Registering the clone after recursing lets a cycle create duplicate copies and recurse forever.