Why it works
- A depth-first walk from the given node reaches every node of a connected graph, and clone(node) copies each one it reaches.
- A cycle brings the walk back to a node it has already started, and a node can be reached from two sides, like 3 here. The map old → copy is filled before the neighbours are visited, so such a node is found in it and its copy is reused: no second copy, no endless loop.
- Every neighbour of a copy is what clone returned, and clone returns only copies, so no link of the copy leads into the old graph.
Complexity
Time O(V + E): each node is copied once and each edge is looked at from both ends. Memory O(V): the map, and a call stack up to V deep.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗