```
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node != NULL){
std::vector<UndirectedGraphNode*> nodesQueue;
nodesQueue.push_back(node);
size_t curPos = 0;
while(curPos < nodesQueue.size()){
UndirectedGraphNode *curNode = nodesQueue[curPos];
++curPos;
UndirectedGraphNode *newNode = new UndirectedGraphNode(curNode -> label);
curNode -> neighbors.push_back(newNode); //At the first time, insert the new node to the end of the old node and just left the neighbors empty
int len = curNode -> neighbors.size() - 1;
for(int i = 0; i < len; ++i){ //Push all the neighbors of current node to the queue
if(curNode -> neighbors[i] != curNode && find(nodesQueue.begin(), nodesQueue.end(), curNode -> neighbors[i]) == nodesQueue.end()){//Not a node that point to itself and is a new node
nodesQueue.push_back(curNode -> neighbors[i]);
}
}
}
UndirectedGraphNode *result = node -> neighbors[node -> neighbors.size() - 1];
sort(nodesQueue.begin(), nodesQueue.end());
curPos = 0;
while(curPos < nodesQueue.size()){
UndirectedGraphNode *curNode = nodesQueue[curPos];
++curPos;
int len = curNode -> neighbors.size() - 1;
UndirectedGraphNode *newNode = curNode -> neighbors[len];
curNode -> neighbors.erase(curNode -> neighbors.end() - 1);
for(int i = 0; i < len; ++i){
if(curNode -> neighbors[i] == curNode){
newNode -> neighbors.push_back(newNode);
}else{
newNode -> neighbors.push_back(curNode -> neighbors[i] -> neighbors[curNode -> neighbors[i] -> neighbors.size() - 1]);
}
}
}
return result;
}
return NULL;
}
};
This is the result, it's clearly that all the clone nodes is a new node rather than a reference
Clone Graph
0(0x94180f8): 1(0x9418140)5(0x9418170)
1(0x9418140): 2(0x9418188)5(0x9418170)
5(0x9418170):
2(0x9418188): 3(0x9418128)
3(0x9418128): 4(0x94181e0)4(0x94181e0)
4(0x94181e0): 5(0x9418170)5(0x9418170)
Original Graph
0(0x9418008): 1(0x9418020)5(0x9418080)
1(0x9418020): 2(0x9418038)5(0x9418080)
5(0x9418080):
2(0x9418038): 3(0x9418050)
3(0x9418050): 4(0x9418068)4(0x9418068)
4(0x9418068): 5(0x9418080)5(0x9418080)
```