I don't even believe it. Its runtime beats 99.7% of cpp submissions.
It saves all the nodes that were created in an unordered_map to avoid some cases.
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
private:
unordered_map<int, UndirectedGraphNode *> m;
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL) {
return NULL;
}
UndirectedGraphNode *ans = new UndirectedGraphNode(node->label);
m[ans->label] = ans;
if(node->neighbors.size() == 0) {
return ans;
}
UndirectedGraphNode *tmp;
while(node->neighbors.size()) {
tmp = *(node->neighbors.begin());
node->neighbors.erase(node->neighbors.begin());
if(m.find(tmp->label) != m.end()) {
tmp = m[tmp->label];
} else {
tmp = cloneGraph(tmp);
}
if(tmp != NULL) {
ans->neighbors.push_back(tmp);
}
}
return ans;
}
};