PREP50 Editorial

editorial
1

Problem Explanation

We are given a root of an undirected graph. We have to clone that graph and return the root of the clone graph

Approach

We iterate through the graph the create a new node for each node and call the function for all it’s children. The function returns the pointer to the new node it just cloned, which is pushed into the neighbors array of the parent node.

Code

class Solution {
public:
    map<Node*, bool> vis;
    Node* cloneGraph(Node* node) {
        if(node==nullptr) return nullptr;
        vis[node] = true;
        Node* curnode = new Node(node->val);
        for(auto i: node->neighbors){
            if(!vis[i])
            curnode->neighbors.push_back(cloneGraph(i));
        }
        return curnode;
    }
};