```
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node)
return NULL;
stack<UndirectedGraphNode*> dfs;
unordered_set<int> visited; // nodes we've already deep copied
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> nodes; // map from orig -> copied
dfs.push(node);
while(!dfs.empty()) {
UndirectedGraphNode *n = dfs.top();
dfs.pop();
if(visited.find(n->label) == visited.end()) {
visited.insert(n->label);
// create the node if it doesn't exist
if(nodes.find(n) == nodes.end()) {
UndirectedGraphNode *c = new UndirectedGraphNode(n->label);
nodes[n] = c;
}
// populate the node's neighbors, creating nodes if they already weren't created previously
for(auto p : n->neighbors) {
if(nodes.find(p) == nodes.end()) {
nodes[p] = new UndirectedGraphNode(p->label);
}
nodes[n]->neighbors.push_back(nodes[p]);
if(visited.find(p->label) == visited.end())
dfs.push(p);
}
}
}
return nodes[node];
}
};
```