Clone Graph

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Examples

The brute-force approach

Traverse the graph to collect all nodes, then create clones, then wire up all neighbor references in a second pass.

# Two-pass: first create all clones, then set neighbors
nodes = bfs_collect_all(start)
clones = {n: Node(n.val) for n in nodes}
for n in nodes:
    clones[n].neighbors = [clones[nei] for nei in n.neighbors]
return clones[start]

Actually O(V + E), which is optimal — it's just a two-pass version of what a single DFS does in one pass with a visited map.

Spotting the pattern

This is a Graph Traversal problem. The key question to ask yourself:

What happens if you don't check the map before recursing? Imagine node A has neighbor B, and B has neighbor A. What goes wrong?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.