Time Cost

12min07s

Implementation

Breadth-First Search

Code

• Solution

  class Solution {
  public:
    Node* cloneGraph(Node* node) {
        if(node == NULL)
            return node;
          
        // to keep map of their edges
        unordered_map<Node*, Node*> visited;
        // to keep nodes which are not visited 
        queue<Node*> Q;
          
        // add first node as visited and add it into the queue
        visited[node] = new Node(node->val);
        Q.push(node);
          
        while(!Q.empty()) {
            // take the node 
            Node* curr = Q.front();
            Q.pop();
              
            // explore all its neighbors and their nodes
            for(auto nei : curr->neighbors) {
                // if not visited add it
                if(!visited[nei]) {
                    visited[nei] = new Node(nei->val);
                    Q.push(nei);
                }
                // if it is visited add its edges
                visited[curr]->neighbors.push_back(visited[nei]);
            }
        }
        // return the visited intial(first) node;
        return visited[node];
  
    }
  };