We want to return a copy of a graph. The graph is not necessarily a DAG, so cycles have to be considered.
I prefer DFS, and it works fine for this problem — you create a copy of each node and then for each of its neighbors, you visit each of its neighbors into a list as well. Finally, you return the copy of your current node, since you need to return something for the neighbors list to be populated.
If we’ve already visited a node, return its cached copy.
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
copies = {None: None}
def visit(node):
if node in copies:
return copies[node]
copies[node] = Node(node.val)
copies[node].neighbors = [visit(neighbor) for neighbor in node.neighbors]
return copies[node]
return visit(node)