Clone Graph

Problem

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the entire graph. Each node has a value and a list of neighbor references; the clone must be structurally identical (same connectivity) but made of entirely new node objects. (LeetCode 133.)

Examples

The square graph this adj list describes:

1 -- 2
|    |
4 -- 3

Cloned-1 must connect to cloned-2 and cloned-4, and so on — same connectivity, all new nodes.

Constraints

up to 100 nodes, connected graph, no self-loops or repeated edges.

Attempt it first

The graph can have cycles (it's explicitly undirected and connected, which almost always means cycles), so a naive DFS/BFS that creates a new clone every time it visits a node would infinite-loop or create duplicate clones of the same original node. Before opening anything, think about what single piece of extra state, tracked during the traversal, prevents both problems at once.