You are given a reference to one node of a connected undirected graph. Each Node has an integer val and a list neighbors. Return a deep copy of the whole graph: brand new nodes with the same values and the same connections, and no reference to any original node. In the tests, the graph is written as an adjacency list where node i (1-indexed) has value i, and you receive node 1.
- 0 <= number of nodes <= 100
- 1 <= Node.val <= 100 and values are unique
- No repeated edges and no self-loops
- The graph is connected
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Copying a tree is a simple recursion, but a graph has cycles: node 1 points to 2 and 2 points back to 1, so a plain recursion never ends and would also create duplicate copies. The fix is a hash map from original node to clone. It works as the visited set and lets us find the copy of any neighbour. During BFS, the first time we meet a node we create its clone and queue it; for every edge we add the neighbour's clone to the current clone's list.
Algorithm
- If the input node is null, return null.
- Create a clone of the start node, store
map[start] = cloneand push the start node into a queue. - Pop a node
cur. For each neighbournb: if it has no clone yet, create one, store it and queuenb. - Append
map[nb]tomap[cur].neighbors. - When the queue is empty, return
map[start].
O(V + E)Space: O(V) for the map and queueclass Solution: def cloneGraph(self, node: Optional['Node']) -> Optional['Node']: if node is None: return None clone = {node: Node(node.val)} # original -> copy queue = deque([node]) while queue: cur = queue.popleft() for nb in cur.neighbors: if nb not in clone: # first time we see nb clone[nb] = Node(nb.val) queue.append(nb) clone[cur].neighbors.append(clone[nb]) return clone[node]