C++ DFS and BFS solution using unordered_map


  • 2
    S
    /**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    class Solution {
    private:
        unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> hash;
    public:
        //BFS
         UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
             if(!node) return NULL;
             queue<UndirectedGraphNode*> Qu;
             Qu.push(node);
             hash[node] = new UndirectedGraphNode(node->label);
             while(!Qu.empty()){
                 UndirectedGraphNode * tmp = Qu.front();
                 Qu.pop();
                 for(UndirectedGraphNode * neighbor : tmp->neighbors){
                     if(hash.find(neighbor) == hash.end()){
                         hash[neighbor] = new UndirectedGraphNode(neighbor->label);
                         Qu.push(neighbor);
                     }
                     hash[tmp]->neighbors.push_back(hash[neighbor]);
                 }
             }
             return hash[node];
         }
        //DFS
        UndirectedGraphNode *cloneGraph1(UndirectedGraphNode *node) {
            if(!node) return NULL;
            if(hash.find(node) == hash.end()){
                hash[node] = new UndirectedGraphNode(node->label);
                for(UndirectedGraphNode* neighbor : node->neighbors){
                    hash[node]->neighbors.push_back(cloneGraph1(neighbor));
                }
            }
            return hash[node];
        }
    };

  • 0
    Y

    In DFS solution, I think there is a typo when pushing back the neighbor. cloneGraph should be cloneGraph1.


  • 0
    S

    Yes, you r right, I have already changed it. Thanks


Log in to reply
 

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