# [leetcode] Clone Graph

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()){ 