Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities

describe

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

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

Example 1:

Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]] Output: [[2, 4], [1, 3], [2, 4], [1, 3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).Copy the code

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Copy the code

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Copy the code

Note:

The number of nodes in the graph is in the range [0, 100]. 1 <= Node.val <= 100 Node.val is unique for each node. There are no repeated edges and no self-loops in the graph.  The Graph is connected and all nodes can be visited starting from the given node.Copy the code

parsing

Given a reference to a node in an undirected graph. Returns a deep clone of the graph. Each Node in the diagram contains a value (int) and a List of its neighbors (List[Node]). The format is as follows:

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

And each node has the same value as its index, such as 1 for the first node, 2 for the second, and so on.

Nodes are called BFS nodes, and its neighbors fill the nodes with new values. Nodes are called BFS nodes, and neighbors fill the nodes with new values. Initialize a new node, root, with the value of node. Stack is used for BFS traversal, and visit is used to fill the neighbors and prevent repeated traversal of nodes. Return if node is empty.

The time complexity is O(N), and the space complexity is O(N).

answer

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node: return node
        root = Node(node.val)
        stack = [node]
        visit = {}
        visit[node.val] = root
        while stack:
            top = stack.pop()
            for n in top.neighbors:
                if n.val not in visit:
                    stack.append(n)
                    visit[n.val] = Node(n.val)
                visit[top.val].neighbors.append(visit[n.val])
        return root
		
Copy the code

The results

Linked to the Clone Graph in the linked list. Memory Usage: Each node in the Python online submission list for Clone Graph.Copy the code

The original link

Leetcode.com/problems/cl…

Your support is my biggest motivation