The machine must produce a deep copy of a connected undirected graph: new node objects with the same values and the same adjacency structure, where clone edges mirror original edges exactly. A shallow copy that reuses original nodes fails the problem.
The key insight is the visited map. The machine needs a mapping from every original node to its clone so that when a neighbor is encountered a second time — which is guaranteed in an undirected graph — the traversal reuses the existing clone instead of creating a second one. The map also serves as the visited set, preventing infinite loops on cycles.
The approach has three steps. First, if the input node is null, return null. Second, create the clone of the current node and store it in the map before recursing — storing before exploring children is what breaks cycles. Third, for each neighbor of the original, recurse to get (or retrieve) its clone and append it to the current clone's neighbors. Each node is cloned once and each edge copied once, so time is O(V + E) and space is O(V) for the map and stack.
The trickiest edge case is the self-loop: a node whose neighbor list contains itself. Because the map is written before the recursion descends, the clone can look up its own clone while building neighbors instead of looping forever. The empty-graph edge case returns null.
def cloneGraph(node):
if not node:
return None
clones = {}
def dfs(orig):
if orig in clones:
return clones[orig]
copy = Node(orig.val)
clones[orig] = copy
for n in orig.neighbors:
copy.neighbors.append(dfs(n))
return copy
return dfs(node)