Hints — p22 Clone Graph

Read one at a time.

Hint 1 — The cycle problem. A naive “recurse into each neighbor and copy” enters an infinite loop the moment it hits a back-edge (any edge from a descendant back to an ancestor). You need a way to say “wait, I’ve already started cloning this node — here’s the in-progress new version.”

Hint 2 — Memo as the answer. A dict old_node → new_node. When you arrive at an old node, first check the memo. If present, return the existing new copy. If absent, create the new copy AND register it in the memo BEFORE recursing into neighbors.

Hint 3 — The critical ordering.

new = Node(old.val)
memo[old] = new           # <-- THIS LINE
new.neighbors = [dfs(n) for n in old.neighbors]

The memo write MUST precede the recursive call. Otherwise the recursion that re-encounters old (via a back-edge) sees an empty memo and starts a fresh clone — infinite loop.

Hint 4 — Three roles for one dict. The memo is doing three jobs at once:

1. “Have I seen this old node?” (dedup)
2. “Don’t infinite-loop on cycles” (cycle break)
3. “When I need to attach an edge to a neighbor, give me the cloned version, not the original” (cross-reference) This is why a set doesn’t suffice — you need the dict’s value for role 3.

Hint 5 — Test for independence, not just isomorphism. A clone that shares node objects with the original is a wrong clone, even though it “looks identical.” After cloning, mutate the clone (e.g., clear all neighbors) and confirm the original is untouched. This catches the “I returned node instead of cloning” bug AND the “I aliased the neighbor list” bug.

If still stuck: look at clone_graph_dfs in solution.py — it’s 10 lines and the line ordering tells the whole story.