Clone Graph

Problem

You are handed a reference to one node of a connected, undirected graph. Each node stores an integer val (unique across the graph, numbered 1..n) and a list neighbors of adjacent nodes. Produce a deep copy of the entire graph: a new set of node objects with the same values and the same adjacency, sharing no object with the original. Return the copy of the node you were given. If the input is None, return None.

• The graph has at most 500 nodes; it may also be empty (the reference is None).
• Node values are distinct.
• The graph is undirected: if a lists b, then b lists a. There are no self-loops or repeated edges.
• The graph is connected, so every node is reachable from the given one.

The Node class is part of the interface:

class Node:
    def __init__(self, val: int = 0, neighbors: list["Node"] | None = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Examples

• Adjacency {1: [2], 2: [1, 3, 4], 3: [2], 4: [2]} (a star centred on node 2), given node 1 → a new star with identical adjacency, returned at the copy of node 1. Node 2's copy must be created once even though it is reached from three different neighbors.
• Adjacency {1: [2, 3, 5], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [1, 4]} (six edges forming three overlapping 4-cycles), given node 1 → a copy with the same five nodes and six edges, none of the objects shared with the original.
• None → None.

Hints

1. Walking the graph naively and creating a new node for every neighbor you see will loop forever on a cycle. What information stops you?
2. Each original node must map to exactly one clone. What data structure gives you "have I cloned this yet, and if so which object is it?"
3. DFS (or BFS) with a hash map from original node to its clone. Create the clone before recursing into neighbors so that back-edges find it in the map.