133. Clone Graph

Clone Graph problem on LeetCode (Medium)

Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. The key idea is to use DFS or BFS with a hashmap that maps each original node to its cloned node. This prevents duplicate clones and also prevents infinite loops in cyclic graphs.

DFS Hashmap Solution:
Time Complexity: O(V + E)
Space Complexity: O(V)

We start from the given node and clone it. Before exploring its neighbors, we immediately save it in a hashmap:

oldToNew[old_node] = cloned_node

Then for each neighbor, we call DFS and append the returned cloned neighbor to the current clone’s neighbor list:

copy.neighbors.append(dfs(neighbor))

If the neighbor has already been cloned, DFS simply returns the existing clone from the hashmap. If not, DFS creates it. This is why we do not create duplicate nodes.

The important detail is that each node appends neighbors only to its own cloned neighbor list. So when old2 sees old1, it appends new1 to new2.neighbors. Later, when old1 sees old2, it appends new2 to new1.neighbors. That is not duplication — that is exactly how an undirected graph stores an edge from both sides.

Видео 133. Clone Graph канала JunCodes