133. Clone Graph
You are handed one node of a connected, undirected graph and must build a complete deep copy of it. Each node carries an integer value val and a list neighbors of adjacent nodes; in a graph with n nodes the values are exactly 1 through n, and you receive the node whose value is 1 (or nothing at all when the graph is empty — return nothing back in that case).
Your function takes that node and returns the corresponding node of the clone: a brand-new set of node objects with the same values, wired together with the same connections. No node of the original graph may appear anywhere in the copy — the grader checks object identity, so returning or re-using an original node fails even though the values would look right.
The graph has no self-loops and no repeated edges, and every node is reachable from node 1.
Example 1:
Input: node = the graph's node 1, adjacency [[2,4],[1,3],[2,4],[1,3]]
Output: node 1 of a deep copy with identical adjacency
Explanation: The four nodes form a square: 1—2—3—4—1. The clone must reproduce that exact wiring with four brand-new node objects.
Example 2:
Input: node = a lone Node(1) with no neighbors
Output: a new Node(1) with no neighbors
Explanation: A single node with no edges. The clone is one new node with value 1 and an empty neighbor list.
Example 3:
Input: node = node 1 of the graph 1—2
Output: node 1 of a deep copy of 1—2
Explanation: Two nodes joined by one edge; the copy needs two new nodes pointing at each other.
Constraints:
- 0 ≤ n ≤ 100
- Node values are exactly 1..n; you are given the node valued 1 (or nothing when n = 0).
- No self-loops or duplicate edges; the graph is connected.
Hints:
Walking the graph is easy (DFS or BFS); the real problem is cycles. If you naively clone neighbors recursively, the square 1—2—3—4—1 makes you clone node 1 forever. You need to remember which originals you have already copied.
Keep a hash map original → clone. When asked to clone a node: if it is already in the map, return the stored copy; otherwise create the copy, register it in the map before touching neighbors, then fill its neighbor list with clones of the original's neighbors.
Registering the clone in the map before recursing into neighbors is the step that breaks cycles — by the time a cycle loops back to a node, its half-built copy is already findable. The same map doubles as the visited set of the traversal.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: node 1 of the square graph [[2,4],[1,3],[2,4],[1,3]]
Expected output: a deep copy with adjacency [[2,4],[1,3],[2,4],[1,3]]