The problem
A graph is a set of nodes joined by edges. Here each node has a value and a list of its neighbors, and the graph is undirected: every edge is listed at both of its ends.
Given one node of a connected graph, return a deep copy — new nodes with the same values, joined in exactly the same way. It is written here as an adjacency list: row i lists the neighbours of the node with value i + 1.
Examples
- Input
node = [[2, 4], [1, 3], [2, 4], [1, 3]]
- Output
[[2, 4], [1, 3], [2, 4], [1, 3]]
- Input
node = [[]]
- Output
[[]]
- Input
node = []
- Output
[]
Constraints
- 0 ≤ number of nodes ≤ 100
- 1 ≤ Node.val ≤ 100, each different
- No repeated edges and no node joined to itself.
- The graph is connected.
The idea
Walk the graph, copying each node as it is first met. The danger is cycles: node 1’s neighbour is 2, whose neighbour is 1 again. Copying naively would go round forever, or make two copies of node 1.
So keep a hash map from each original node to its copy. Before copying a node, check the map; if it is there, reuse the copy. And record the copy in the map before copying the neighbours — then a cycle back to this node finds its copy already waiting.
- Time
- O(V + E) — each node and edge once
- Space
- O(V) — the map
Solution · every language run against every case
class Solution: def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]: copies = {} # original node -> its copy def clone(n): if n in copies: return copies[n] copy = Node(n.val) copies[n] = copy # recorded before the neighbours, so a cycle back to n finds it copy.neighbors = [clone(m) for m in n.neighbors] return copy return clone(node) if node else None