133.-clone-graph.md

133. Clone Graph

{% tabs %} {% tab title="C++" %}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return NULL;
        
        Node* newHead = new Node(node->val, {}); // initial the new head
        unordered_map<Node*,Node*> visited;
        queue<Node*> q;
        visited[node] = newHead;
        q.push(node);
        while (!q.empty()){
            Node* node = q.front();
            q.pop();
            
            for (auto neighbor : node->neighbors){
                if (visited.find(neighbor) == visited.end()){
                    visited[neighbor] = new Node(neighbor->val, {});
                    q.push(neighbor);
                }
                // neighbors is a vector
                visited[node]->neighbors.push_back(visited[neighbor]);
                
            }
        }
        return newHead;
        
        
    }
};

{% endtab %}

{% tab title="Python" %}

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        ## 上限100

        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return 
        from collections import deque
        q = deque()
        visited = dict() # node都有邻居 不需担心空value
        q.append(node)
        node_copy = Node(node.val, [])
        visited[node] = node_copy
        while q:
            node = q.popleft()
            if not node:
                continue
            for neightbor in node.neighbors:
                if neightbor not in visited:
                    visited[neightbor] = Node(neightbor.val, [])
                    q.append(neightbor)
                visited[node].neighbors.append(visited[neightbor])
        return node_copy

{% endtab %} {% endtabs %}