leetcode Clone Graph

Clone Graph  
Total Accepted: 2649 
Total Submissions: 14045 My Submissions
Clone an undirected graph. Each node in the graph contains a  label  and a list of its  neighbors .
OJ's undirected graph serialization:
Nodes are labeled uniquely. We use  #  as a separator for each node, and  ,  as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph  {0,1,2#1,2#2,2} .
The graph has a total of three nodes, and therefore contains three parts as separated by  # .

First node is labeled as  0 . Connect node  0  to both nodes  1  and  2 .

Second node is labeled as  1 . Connect node  1  to node  2 .

Third node is labeled as  2 . Connect node  2  to node  2  (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

DFS is OK, TAKE NOTICE the position of

      exist.insert(make_pair(node, nodecpy));

The following is the AC code:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
 public:
  UndirectedGraphNode *DFS(UndirectedGraphNode *node, unordered_map& exist) {
    if (exist.find(node) != exist.end())
      return exist[node];
    else {
      UndirectedGraphNode *nodecpy = new UndirectedGraphNode(node->label);
      exist.insert(make_pair(node, nodecpy));
      UndirectedGraphNode *neighbor = NULL;
      for (int i = 0; i < (node->neighbors).size(); ++i) {
        neighbor = DFS((node->neighbors)[i], exist);
        (nodecpy->neighbors).push_back(neighbor);
      }
      return nodecpy;
    }
      
  }
  UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    unordered_map exist;
    if (node == NULL)
      return node;
    return DFS(node,exist);
  }
};