Leetcode 133. Clone Graph: DFS deep copy is not getting accepted

Question

I am trying to solve LeetCode problem 133. Clone Graph:

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on.

I used a DFS traversal to do a deep copy along the way, but it is not getting accepted. I tried printing out the node values and its memory addresses of the original and copy, side by side, and I don't understand why my deep copy wouldn't pass as a working solution. I commented out the unnecessary lines for testing.

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return 
        if not node.neighbors:
            return Node(node.val)
        

        ans = Node(node.val,[])
        visited = set()

        def dfs(node,copy):
            if not node or node.val in visited:
                return
            visited.add(node.val)
            neighbors = node.neighbors
            for neighbor in neighbors:
                deepcopy = Node(neighbor.val)
                copy.neighbors.append(deepcopy)

                dfs(neighbor,deepcopy)

        dfs(node,ans)
        
        # test = set()
        # def dfsTest(og,copy):
        #     if og in test:
        #         return 
            
        #     test.add(og)
        #     og_n = og.neighbors
        #     copy_n = copy.neighbors

        #     for o,c in zip(og_n,copy_n):
        #         print(o,c)  
        #         print(o.val,c.val)
        #         dfsTest(o,c)  
        
        # dfsTest(node,ans)
        return ans

Answer 1

The problem is that your code cannot produce a graph that has cycles. Yet this must be supported, because the input graph can have cycles, and it is for those test cases your code will fail.

It creates a new Node (deepcopy) for a neighbor, even if that neighbor was already visited. In that case, you had already created a copy for the (neighbor) node, and you should reuse it at this point instead of creating yet another copy.

To achieve that, I would suggest turning visited into a dictionary, so that when you detect that a node was already visited, you can also retrieve the copy that was created for it.

Unrelated remarks

• I would not use a second argument for dfs. Instead let it return the copied node.
• There is no need to treat an empty input graph, or a single-node graph any different from other graphs: dfs will deal with those just fine.

Correction

Here is a correction of your code that implements that idea:

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        visited = {}  # not a set, but a dict

        def dfs(node):
            if not node:
                return
            if node.val in visited:  # already visited
                return visited[node.val]  # get the copy we already created for it
            copy = Node(node.val)
            visited[node.val] = copy  # remember the copy we created for this node
            for neighbor in node.neighbors:
                deepcopy = dfs(neighbor)
                copy.neighbors.append(deepcopy)
            return copy  # return the copy instead of using a parameter

        return dfs(node)

You can shorten this code a bit by using map() and combining two cases with one return:

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        visited = {}

        def dfs(node):
            if node:
                copy = visited.get(node.val)
                if not copy:
                    copy = visited[node.val] = Node(node.val)
                    copy.neighbors = list(map(dfs, node.neighbors))
                return copy

        return dfs(node)