Description
Deep-copy a connected undirected graph, preserving values and edges. Examples use adjacency lists for nodes numbered from 1; an empty list represents no graph.
Solution
from collections import deque
def clone_graph(node):
if not node:
return None
copies = {node: Node(node.val)}
queue = deque([node])
while queue:
original = queue.popleft()
for neighbor in original.neighbors:
if neighbor not in copies:
copies[neighbor] = Node(neighbor.val)
queue.append(neighbor)
copies[original].neighbors.append(copies[neighbor])
return copies[node]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[2],[1]]]- Output
[[2],[1]]
The copy retains the two reciprocal edges.
Example 2
- Input
[[[]]]- Output
[[]]
The isolated node is still copied.
Example 3
- Input
[[]]- Output
[]
No input node means no output node.
Approach
Map original nodes to newly allocated nodes and traverse neighbors with a queue.
Time & space
O(V + E) time; O(V) auxiliary space, excluding the copied graph. V is the vertex count, E the edge count; R and C denote grid dimensions when used.