Depth First Iterative C++ solution


  • 0
    Z

    BFS iterative or DFS recursive solutions are more proper for this problem, as shown in other posts. Here is my DFS iterative solution in C++, just for fun and exercise.
    An unordered_map is used to map from original nodes to copied nodes. Two stacks of the same size are used, one is for the Graph nodes in DFS visit, and the second stack is to keep the index in the neighbors to visit in next round. When moving backward in DFS (stack pops), we should start from the most recently visited neighbor rather than from the beginning. This is why I need a second stack of index.

     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if (!node) return NULL;
            UndirectedGraphNode *ans = new UndirectedGraphNode(node->label);
            // Using two stacks for DFS, first stack for the node p, and second stack 
            // for the index of p->neighbors to visit in the next round
            stack<UndirectedGraphNode*> s; 
            stack<int> idx;
            s.push(node);
            idx.push(0);
            // map from original nodes to copied nodes
            unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
            map[node] = ans;
            while (!s.empty()) {
                UndirectedGraphNode *p = s.top();
                int sz = s.size(); 
                // if a node in p->neighbors has been visited, add it to map[p]'s neighbors;
                // otherwise, make a copy, update the index to visit, and two stacks push;
               //  In the second case, a new node is discovered, break the loop and visit deeper
                for (int i = idx.top(); i < p->neighbors.size(); ++i) {
                    if (map.find(p->neighbors[i]) != map.end()) 
                        map[p]->neighbors.push_back(map[p->neighbors[i]]);
                    else {
                        map[p->neighbors[i]] = new UndirectedGraphNode(p->neighbors[i]->label);
                        map[p]->neighbors.push_back(map[p->neighbors[i]]);
                        idx.top() = i+1;
                        s.push(p->neighbors[i]);
                        idx.push(0);
                        break;
                    }
                    
                }
                // if stack size doesn't increase, no new node is discovered, so pop
                if (sz == s.size()) {
                    idx.pop();
                    s.pop();
                }
            }
            return ans;
    

Log in to reply
 

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