Clone Graph

Given a reference to a node in a connected graph, return a deep copy of the graph. Each node has a Val and a list of Neighbors.

Function signature

func CloneGraph(node *Node) *Node

Inputs / outputs

• node: a pointer to any node in the graph (may be nil).
• Return: the cloned node corresponding to node.

Example

1 -- 2
|  / |
3 -- 4
Output: a new graph with the same connections

Constraints

• 0 <= number of nodes <= 100_000
• node values are unique within the graph

Core idea (near-solution)

Use DFS/BFS with a map from original nodes to cloned nodes so each node is copied exactly once and cycles are handled safely.

Invariant: if a node exists in the map, its clone is already fully or partially constructed and must be reused.

Algorithm (step-by-step)

1. If node is nil, return nil.
2. Create copies := map[*Node]*Node.
3. DFS/BFS starting from node:
   • If the current node is not in copies, create its clone and store it.
   • For each neighbor:
     • If the neighbor is not in copies, create its clone and enqueue/recurse.
     • Append the neighbor's clone to the current clone's neighbor list.
4. Return copies[node].

Correctness sketch

• Invariant: if a node exists in the map, its clone is already fully or partially constructed and must be reused.
• DFS visits exactly all nodes reachable from a start node.
• Marking visited prevents revisits and guarantees termination.
• Repeating from unvisited nodes correctly handles all components.

Trace (hand walkthrough)

Example input:
1 -- 2
|  / |
3 -- 4
Output: a new graph with the same connections

Walk:
- clone node 1; enqueue neighbors 2 and 3
- clone nodes 2,3,4 and wire edges as neighbors are visited
- resulting cloned graph has same 1-2-3-4 connections

Pitfalls to avoid

• Using node values as map keys (values are unique here, but pointers are safer).
• Creating neighbor clones without storing them first (causes duplicate nodes).
• Forgetting to handle nil input.

Complexity

• Time: O(V + E) where V is nodes and E is edges.
• Extra space: O(V) for the map and recursion/queue.

Implementation notes (Go)

• Use map[*Node]*Node and a slice queue or recursion.
• Append neighbor clones in the same order as the original neighbors to preserve adjacency ordering.