/**

 * Definition for undirected graph.

 * struct UndirectedGraphNode {

 *     int label;

 *     vector<UndirectedGraphNode *> neighbors;

 *     UndirectedGraphNode(int x) : label(x) {};

 * };

 */

 typedef UndirectedGraphNode NODE;

 typedef pair<NODE*, NODE*> PAIR;

 NODE* dfs(NODE *node, unordered_map<NODE*, NODE*> &_map) {

     if(_map.count(node)) return _map[node];

     NODE *p = new NODE(node->label);

     _map.insert(PAIR(node, p));

     for(size_t i = 0; i < node->neighbors.size(); ++i) {

         p->neighbors.push_back(dfs(node->neighbors[i], _map));

     }

     return p;

 }

class Solution {

public:

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

        unordered_map<NODE*, NODE*> _map;

        _map[NULL] = NULL;

        return dfs(node, _map);

    }

};