Clone Graph

LeetCode

LeetCode: https://leetcode.com/problems/clone-graph/

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

1def cloneGraph(node: 'Node') -> 'Node':
2    if not node:
3        return None
4        
5    copies = {}
6    
7    def dfs(cur: 'Node') -> 'Node':
8        if cur in copies:
9            return copies[cur]
10        copy = Node(cur.val)
11        copies[cur] = copy
12        for nei in cur.neighbors:
13            copy.neighbors.append(dfs(nei))
14        return copy
15    
16    return dfs(node)
Next
Course Schedule
cur
[2,4]
0
[1,3]
1
[2,4]
2
[1,3]
3
copies={}
Step 1 / 7
Step 1:
Represent the graph as an adjacency list and start DFS from node 1.
Pointers: cur=0
Focus: select @ [0]