Copy a graph with a map

Before you start

• Hashing

  The clone map is a dict from each original node to its copy.

  Open lesson

Why it matters

Snapshots, document duplication, and object serialization must copy structures whose references can be shared or cyclic. A careless copy can recurse forever, duplicate one shared object into several objects, or leave new nodes pointing back into the original. The copy must preserve every edge and shared identity without duplicating a node or retaining an original reference.

The graph is given as an adjacency list (neighbors[i] is the 1-based neighbors of node i+1). Return a deep copy as an adjacency list in the same node order.

Input

adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]

Output

[[2, 4], [1, 3], [2, 4], [1, 3]]

For [[2, 4], [1, 3], [2, 4], [1, 3]], naive recursion follows 1 → 2 → 1 forever. Record 1′ before visiting 2 or 4, so the return edge finds 1′ immediately and each original gets one copy.

For adjacency [[2, 4], [1, 3], [2, 4], [1, 3]], create 1′ and store original 1 → 1′ before following neighbors 2 and 4. From 2, create 2′, then continue to 3 and 4 in the same way.

When 2 reaches neighbor 1, the map already contains 1′, so return that object and link 2′ to it instead of recursing again. Each later revisit does the same. The finished copies have the same square of edges, but every neighbor reference points to a primed node.