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 / \ \_/

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]; } };