Clone Graph

The problem description can be found in LeetCode.

Approach

In this problem, we just need a way to traverse the Graph, and then clone the current node, plus its children.

However, we need to be careful about possible cycles. In fact, if we have a simple Undirected Graph with two nodes, we need a way to keep track of the first node we have already cloned. Otherwise, when we try to clone the neighbors of the second node, we would visit the first node again.

We can keep track of a mapping between the old nodes and the new ones. In this way, we can simply return the node we have already cloned if it is processed twice.

Solution

from typing import Dict, Optional


class Solution:
    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
        def dfs(
            node: Optional["Node"], old_to_new: Dict["Node", "Node"]
        ) -> Optional["Node"]:
            if not node:
                return None
            if node in old_to_new:
                return old_to_new[node]

            new_node = Node(node.val, [])
            old_to_new[node] = new_node
            for neighbor in node.neighbors:
                new_node.neighbors.append(dfs(neighbor, old_to_new))

            return new_node

        return dfs(node, {})

Complexity

• Time: $O(E+V)$
• Space: $O(V)$

Where $E$ and $V$ are the number of edges and vertices of the input graph, respectively.