21.md

Clone undirected graph

Node* dfs(Node* cur,unordered_map<Node*,Node*>& m)
    {
        vector<Node*>nei;
        
        Node* clone=new Node(cur->val);
        m[cur]=clone;
        
        for(auto it:cur->neighbors)
        {
            if(m.find(it)!=m.end())
                nei.push_back(m[it]);
                
            else
                nei.push_back(dfs(it,m));
        }
        
        clone->neighbors=nei;
        return clone;
    }
    Node* cloneGraph(Node* node) {
        
        unordered_map<Node*,Node*>m;
        
        if(node==NULL)              //given empty
            return NULL;
            
        if(node->neighbors.size()==0)          //given 1 node
        {
            Node* clone=new Node(node->val);
            return clone;
        }
        
        return dfs(node,m);
    }

Method 2(BFS)

 Node* cloneGraph(Node* node) {
        
        unordered_map<Node*,Node*>m;
        
        if(node==NULL)              //given empty
            return NULL;
            
        if(node->neighbors.size()==0)          //given 1 node
        {
            Node* clone=new Node(node->val);
            return clone;
        }
        
        queue<Node*>q;
        
        q.push(node);
        Node* start;
        int flag=0;
        
        m[node]=new Node(node->val);
        
        while(!q.empty())
        {
            Node* cur=q.front();
            q.pop();
            
            
            for(auto it: cur->neighbors)
            {
        
               
               if(m.find(it)==m.end())
                {
                    Node* new_clone=new Node(it->val);
                    m[it]=new_clone;
                    
                    //nei.push_back(m[it]);
                    q.push(it);
                }
                
                m[cur]->neighbors.push_back(m[it]);
            }
            
        }
        
        return  m[node];
    }

    ```