Clone map

Give you no direction   connected   A reference to a node in the graph , Please go back to   Deep copy （ clone ）.

Each node in the graph contains its value  val（int） List of neighbors （list[Node]）.

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

Test case format ：

Simplicity , Each node has the same value as its index . for example , The first node value is 1（val = 1）, The second node value is 2（val = 2）, And so on . The diagram uses adjacency lists to represent .

Adjacency list   Is a set of unordered lists used to represent finite graphs . Each list describes the neighbor set of nodes in the graph .

A given node will always be the first node in the graph （ The value is 1）. You have to   Copy of a given node   Returns... As a reference to the clone graph .

Example 1：

 Input ：adjList = [[2,4],[1,3],[2,4],[1,3]]
 Output ：[[2,4],[1,3],[2,4],[1,3]]
 explain ：
 The picture shows 4 Nodes .
node 1 The value of is 1, It has two neighbors ： node 2 and 4 .
node 2 The value of is 2, It has two neighbors ： node 1 and 3 .
node 3 The value of is 3, It has two neighbors ： node 2 and 4 .
node 4 The value of is 4, It has two neighbors ： node 1 and 3 .

Example 2：

 Input ：adjList = [[]]
 Output ：[[]]
 explain ： The input contains an empty list . The graph has only one value of 1 The node of , It doesn't have any neighbors .

Example 3：

 Input ：adjList = []
 Output ：[]
 explain ： This picture is empty , It does not contain any nodes .

Example 4：

 Input ：adjList = [[2],[1]]
 Output ：[[2],[1]]

Tips ：

1. The number of nodes does not exceed 100 .
2. Each node value  Node.val  It's all unique ,1 <= Node.val <= 100.
3. An undirected graph is a Simple picture , This means that there are no duplicate edges in the graph , There is no self link .
4. Because the graph is undirected , If node  p  Is the node  q  Neighbors of , Then the node  q  It must also be a node  p  Neighbors of .
5. A graph is a connected graph , You can access all nodes from a given node .

class Node:
def __init__(self, val=0, neighbors=[]):
self.val = val
self.neighbors = neighbors
class Solution:
def cloneGraph(self, node: "Node") -> "Node":
marked = {}
def dfs(node):
if not node:
return node
if node in marked:
return marked[node]
clone_node = Node(node.val, [])
marked[node] = clone_node
for neighbor in node.neighbors:
clone_node.neighbors.append(dfs(neighbor))
return clone_node
return dfs(node)