1 /** 2  * Definition for undirected graph. 3  * struct UndirectedGraphNode { 4  *     int label; 5  *     vector<UndirectedGraphNode *> neighbors; 6  *     UndirectedGraphNode(int x) : label(x) {}; 7  * }; 8  */ 9 class Solution {10 public:11     /**12      * @param node: A undirected graph node13      * @return: A undirected graph node14      */15     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {16         // write your code here17         18         // suppose the value of nodes are unique.19         // For every node, construct a new node of the same value. For its neighbours, first check if the neighbour has been created (value equals or not), if not, create a node and push into a queue, if so, link the it to the neighbor. 20         // To check whether the neighbour has been visited, maintain a hash map to map the original node to a newly created node.21         if (!node) return node;22         queue<UndirectedGraphNode* > qu;23         qu.push(node);24         unordered_map<UndirectedGraphNode*, UndirectedGraphNode* > um;25         UndirectedGraphNode* result = new UndirectedGraphNode(node->label);26         um[node] = result;27         while (!qu.empty()) {28             UndirectedGraphNode* temp = qu.front();29             qu.pop();30             UndirectedGraphNode* move = um[temp];31             32             for (auto neighbor : temp->neighbors) {33                 // if the neighbor is not created, created it and map neighbor to a new create node, update the neighbor of move with newly created node34                 if (um.find(neighbor) == um.end()) {35                     UndirectedGraphNode* newNeighbor = new UndirectedGraphNode(neighbor->label);36                     um[neighbor] = newNeighbor;37                     move->neighbors.push_back(newNeighbor);38                     qu.push(neighbor);39                 } else {40                     move->neighbors.push_back(um[neighbor]);41                 }42             }43         }44         return result;45     }46 };