 Given a node in a graph `node`, clone the graph, and return the cloned node. When you modify the cloned graph, it should have no effect on the original graph. This means that you can't simply return the original node as the solution to the problem. sc1 We want to write a function that takes in a `node`, and returns its clone. ``cloneGraph(node)`` sc2 To write the recursion, we first have to copy the current node. After we do this, we need to point the node to the clones of its neighbor nodes, l

Clone Graph



-----problem-----
    

Given a node in a graph `node`, clone the graph, and return the cloned node. 

When you modify the cloned graph, it should have \b{no effect} on the original graph. This means that you can't simply return the original node as the solution to the problem.


\split{{
\image{0, 200}
}}{{
\image{1, 200}
}}


-----solution-----


\sc1

We want to write a function that takes in a `node`, and returns its clone.

``cloneGraph(node)`` 

\sc2

To write the recursion, we first have to copy the current node. After we do this, we need to point the node to the clones of its neighbor nodes, like this: 

\image{2, 200}

Here's the recursion:

``
cloneGraph(node) = (    
    # clone the current node
    clone = GraphNode(node.val)
    
    # point the clone to its cloned neighbors
    clone.neighbors = [cloneGraph(nbr) for nbr in node.neighbors] 
    return clone
)
``


\sc3



We need to make sure we don't enter any infinite cycles since we're dealing with graphs. We should stop if we get to a node we've already cloned. This way we never clone the same node twice, so our code can't possibly run forever.

To do this, we'll store all the nodes we've visited in a HashMap called `cloneOfNode`. Here's the base case:

``
if node in cloneOfNode:
    return cloneOfNode[node] # return previously computed clone
``






\sc4

Here's the full code:

\answer



\tc $O(n)$. We visit every node in the graph.

\sc $O(n)$. We store every node in the HashMap `cloneOfNode`.




Recursion

Clone Graph