```
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash;
queue<UndirectedGraphNode*> q;
if (node == NULL) return NULL;
q.push(node);
UndirectedGraphNode* tmp = new UndirectedGraphNode(node->label);
hash[node] = tmp;
while (!q.empty()) {
UndirectedGraphNode* cur = q.front();
UndirectedGraphNode* cur_clone = hash[cur];
UndirectedGraphNode* neighbor_clone;
q.pop();
if (cur->neighbors.empty()) continue;
for (UndirectedGraphNode* neighbor : cur->neighbors) {
if (neighbor == cur) { // circle
cur_clone->neighbors.push_back(cur_clone);
}
else {
if (hash.find(neighbor) == hash.end()) {
neighbor_clone = new UndirectedGraphNode(neighbor->label);
q.push(neighbor);
hash[neighbor] = neighbor_clone;
}
else {
neighbor_clone = hash[neighbor];
}
cur_clone->neighbors.push_back(neighbor_clone);
}
}
}
return hash[node];
}
};
```