algorithms/cloneGraph/cloneGraph.cpp

// Source : https://oj.leetcode.com/problems/clone-graph/
// Author : Hao Chen
// Date   : 2014-10-12

/********************************************************************************** 
* 
* Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
* 
* OJ's undirected graph serialization:
* 
* Nodes are labeled uniquely.
* 
* We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
* 
* As an example, consider the serialized graph {0,1,2#1,2#2,2}.
* 
* The graph has a total of three nodes, and therefore contains three parts as separated by #.
* 
* First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
* Second node is labeled as 1. Connect node 1 to node 2.
* Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
* 
* Visually, the graph looks like the following:
* 
*        1
*       / \
*      /   \
*     0 --- 2
*          / \
*          \_/
* 
*               
**********************************************************************************/

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL) return NULL;
        
        //create a map, key is source node, value is clone node.
        map<UndirectedGraphNode*, UndirectedGraphNode*> cloneMap;
        
        //using queue for breadth first search
        queue<UndirectedGraphNode*> q;
        q.push(node);
        
        //clone the root
        UndirectedGraphNode* cloneNode = new UndirectedGraphNode(node->label);
        cloneMap[node] = cloneNode;
        
        //breadth first search
        while(!q.empty()){
            UndirectedGraphNode* n = q.front();
            q.pop();
            //for each neighbors
            for(int i=0; i<n->neighbors.size(); i++){
                UndirectedGraphNode* neighbor= n->neighbors[i];
                //not existed in cloneMap
                if (cloneMap.find(neighbor)==cloneMap.end()){
                    //clone a node
                    UndirectedGraphNode* newNode = new UndirectedGraphNode(neighbor->label);
                    cloneMap[n]->neighbors.push_back(newNode);
                    cloneMap[neighbor] = newNode;
                    
                    //put the neighbors into the queue
                    q.push(neighbor);
                }else{
                    cloneMap[n]->neighbors.push_back(cloneMap[neighbor]);
                }
            }
        }
        
        return cloneNode;
    }
};