Iterative DFS C++ solution using hash map and stack


  • 0
    B
    class Solution {
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if(!node)
                return NULL;
            stack<UndirectedGraphNode*> dfs;
            unordered_set<int> visited; // nodes we've already deep copied
            unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> nodes; // map from orig -> copied
            dfs.push(node);
            while(!dfs.empty()) {
                UndirectedGraphNode *n = dfs.top();
                dfs.pop();
                if(visited.find(n->label) == visited.end()) {
                    visited.insert(n->label);
                    // create the node if it doesn't exist
                    if(nodes.find(n) == nodes.end()) {
                        UndirectedGraphNode *c = new UndirectedGraphNode(n->label);
                        nodes[n] = c;
                    }
                    // populate the node's neighbors, creating nodes if they already weren't created previously
                    for(auto p : n->neighbors) {
                        if(nodes.find(p) == nodes.end()) {
                            nodes[p] = new UndirectedGraphNode(p->label);
                        }
                        nodes[n]->neighbors.push_back(nodes[p]);
                        if(visited.find(p->label) == visited.end())
                            dfs.push(p);
                    }
                }
            }
            return nodes[node];
        }
    };

  • 0
    I

    In fact you don't need the visited map if you push the orig node only when the copy is created.


Log in to reply
 

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