Accepted : Simple c++ DFS with hash map


  • 6
    L
     typedef UndirectedGraphNode unode;
    class Solution {
    public:
        unordered_map<unode*,unode *> mp;   //maps input node with cloned node
      
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
           if(!node)
            return NULL;
           unode *temp=new unode(node->label);
           mp[node]=temp;
           int len=(node->neighbors).size();
           
           for(int i=0 ; i<len ; i++)
              if(mp[node->neighbors[i]]==0)
           //If input node is not visited,clone it
                (temp->neighbors).push_back(cloneGraph(node->neighbors[i]));   
               else
           //If input node is already visited,simple push the mapped cloned node.
                  (temp->neighbors).push_back(mp[node->neighbors[i]]); 
           return temp;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.