Leetcode 0133. clone diagram

【LetMeFly】133. Clone map ：BFS

Force button topic link ：https://leetcode.cn/problems/clone-graph/

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 .

Method 1 ：BFS

We can traverse the original image through breadth first search

During traversal , If a node is encountered for the first time , Just newly build A node with the same value , And save the new node corresponding to the original node with a hash table

Continue to queue up the nodes you traverse for the first time , Take out one node from the team at a time , Put all its sides , Add to Copy New nodes coming out .

• Time complexity $O(n)$, among $n$ Is the number of nodes
• Spatial complexity $O(n)$

AC Code

C++

class Solution {
    
public:
    Node* cloneGraph(Node* node) {
    
        if (!node)
            return nullptr;
        unordered_map<Node*, Node*> ma;
        queue<Node*> q;
        q.push(node);
        ma[node] = new Node(node->val);
        while (q.size()) {
    
            Node* thisNode = q.front();
            q.pop();
            for (Node* to : thisNode->neighbors) {
    
                if (!ma.count(to)) {
    
                    ma[to] = new Node(to->val);
                    q.push(to);  //  Here is to
                }
                ma[thisNode]->neighbors.push_back(ma[to]);  //  Here is ma[thisNode]
            }
        }
        return ma[node];
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125960776