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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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
         / \
         \_/

Use BFS to traverse the old graph, use a hash table to store the new graph.

Label can not be duplicate.

if node == NULL, return NULL.

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        unordered_map<int, UndirectedGraphNode *> visitedNode;
        queue<UndirectedGraphNode *> q;
        //extreme case
        if(node == NULL) return NULL;
        q.push(node);
        visitedNode[node->label] = new UndirectedGraphNode(node->label);
        while(!q.empty()){
            UndirectedGraphNode * oldNode = q.front();
            q.pop();
            UndirectedGraphNode * newNode = visitedNode[oldNode->label];
            for(auto it = oldNode->neighbors.begin(); it != oldNode->neighbors.end(); it++){
                if(visitedNode.find((*it)->label) == visitedNode.end()){
                    //not found in visitedNode
                    q.push(*it);
                    visitedNode[(*it)->label] = new UndirectedGraphNode((*it)->label);
                }
                newNode->neighbors.push_back(visitedNode[(*it)->label]);
            }
        }
        return visitedNode[node->label];
    }
};