clone_graph 

 1from typing import Optional
 2
 3
 4# @leet start
 5class Node:
 6    def __init__(self, val=0, neighbors=None):
 7        self.val = val
 8        self.neighbors = neighbors if neighbors is not None else []
 9
10
11class Solution:
12    def cloneGraph(self, node: Optional[Node]) -> Optional[Node]:
13        """
14        This problem asks us to clone a graph. To do so, we want to dfs
15        through the provided node and return an exact copy.
16
17        The graph can contain cycles, so we need to have a visited dictionary
18        to break those cycles. The dictionary can contain a copy of the node
19        it's copying, and return that when needed.
20
21        And then for each neighbor we dfs through and add that to our
22        current node's neighbors.
23        """
24        visited = {}
25
26        def dfs(node):
27            if node is None:
28                return None
29            if node in visited:
30                return visited[node]
31            copy = Node(node.val, [])
32            visited[node] = copy
33            copy.neighbors = [dfs(neighbor) for neighbor in node.neighbors]
34            return copy
35
36        return dfs(node)
37
38
39# @leet end
40
41
42def test():
43    assert 2 + 2 == 4
class Node: 
6class Node:
7    def __init__(self, val=0, neighbors=None):
8        self.val = val
9        self.neighbors = neighbors if neighbors is not None else []
Node(val=0, neighbors=None) 
7    def __init__(self, val=0, neighbors=None):
8        self.val = val
9        self.neighbors = neighbors if neighbors is not None else []
val
neighbors
class Solution: 
12class Solution:
13    def cloneGraph(self, node: Optional[Node]) -> Optional[Node]:
14        """
15        This problem asks us to clone a graph. To do so, we want to dfs
16        through the provided node and return an exact copy.
17
18        The graph can contain cycles, so we need to have a visited dictionary
19        to break those cycles. The dictionary can contain a copy of the node
20        it's copying, and return that when needed.
21
22        And then for each neighbor we dfs through and add that to our
23        current node's neighbors.
24        """
25        visited = {}
26
27        def dfs(node):
28            if node is None:
29                return None
30            if node in visited:
31                return visited[node]
32            copy = Node(node.val, [])
33            visited[node] = copy
34            copy.neighbors = [dfs(neighbor) for neighbor in node.neighbors]
35            return copy
36
37        return dfs(node)
def cloneGraph(self, node: Optional[Node]) -> Optional[Node]: 
13    def cloneGraph(self, node: Optional[Node]) -> Optional[Node]:
14        """
15        This problem asks us to clone a graph. To do so, we want to dfs
16        through the provided node and return an exact copy.
17
18        The graph can contain cycles, so we need to have a visited dictionary
19        to break those cycles. The dictionary can contain a copy of the node
20        it's copying, and return that when needed.
21
22        And then for each neighbor we dfs through and add that to our
23        current node's neighbors.
24        """
25        visited = {}
26
27        def dfs(node):
28            if node is None:
29                return None
30            if node in visited:
31                return visited[node]
32            copy = Node(node.val, [])
33            visited[node] = copy
34            copy.neighbors = [dfs(neighbor) for neighbor in node.neighbors]
35            return copy
36
37        return dfs(node)

This problem asks us to clone a graph. To do so, we want to dfs through the provided node and return an exact copy.

The graph can contain cycles, so we need to have a visited dictionary to break those cycles. The dictionary can contain a copy of the node it's copying, and return that when needed.

And then for each neighbor we dfs through and add that to our current node's neighbors.

def test(): 
43def test():
44    assert 2 + 2 == 4