Clone graphy. Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

clone_graph.cpp

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
 
  
class Solution {
public:
   
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        
        //copy nodes first, with old nabor lists
        //after all nodes copied, update nabor list with newly created nodes
        
        //Step 1. copy nodes
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode*> old2New;
        copyNodes(old2New, node);
        UndirectedGraphNode *newNode = old2New[node];
        
        //update nodes
        unordered_set<UndirectedGraphNode*> visited;
        updateNodes(old2New, newNode, visited);
        return newNode;
    }
    void copyNodes(unordered_map<UndirectedGraphNode *, UndirectedGraphNode*> &old2New, UndirectedGraphNode *node) {
        if (!node || old2New.find(node) != old2New.end()) // if copied, exit
            return;
            
        //copy this node
        UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
        old2New[node] = newNode;
        newNode->neighbors = node->neighbors; //old nabors list, to be updated later
        
        for(int i=0; i<node->neighbors.size(); i++) {
            copyNodes(old2New, node->neighbors[i]);
        }
        return;
    }
    
    void updateNodes(unordered_map<UndirectedGraphNode *, UndirectedGraphNode*> &old2New, UndirectedGraphNode *node, unordered_set<UndirectedGraphNode*> &visited) {
        if (!node || visited.find(node) != visited.end()) { //already visited
            return;
        }
        //update this node
        visited.insert(node);
        for(int i=0; i<node->neighbors.size(); i++) {
            node->neighbors[i] = old2New[node->neighbors[i]];
        }    
        for(int i=0; i<node->neighbors.size(); i++) {
            updateNodes(old2New, node->neighbors[i], visited);
        }
        return;
    }
};