Clone Graph

来源：Leetcode

原帖：http://oj.leetcode.com/problems/clone-graph/

题目：
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 from 0 to N - 1, where N is the total nodes in the graph.
We use # as a separator for each node, and , as a separator for each neighbor of the node.
As an example, consider the serialized graph {1,2#2#2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
Connect node 0 to both nodes 1 and 2.
Connect node 1 to node 2.
Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

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

 Solution: 1. DFS. 2. BFS.

代码：

 /**  
  * Definition for undirected graph.  
  * struct UndirectedGraphNode {  
  *   int label;  
  *   vector<UndirectedGraphNode *> neighbors;  
  *   UndirectedGraphNode(int x) : label(x) {};  
  * };  
  */  
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
   //Version 1: DFS, hash-map  
   GraphNode* cloneGraph(GraphNode *node) {  
     MAP map;  
     return cloneGraphHelper(node, map);  
   }  
     
   GraphNode* cloneGraphHelper(GraphNode *node, MAP &map) {  
     if (!node) return NULL;  
     if (map.count(node)) return map[node];        
     GraphNode* newNode = new GraphNode(node->label);  
     map[node] = newNode;  
     for (int i = 0; i < node->neighbors.size(); ++i) {  
       newNode->neighbors.push_back(cloneGraphHelper(node->neighbors[i], map));  
     }  
     return newNode;  
   }  
 };  
   
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
     
   //Version 2: BFS, HashMap  
   GraphNode *cloneGraph(GraphNode *node) {  
     if (!node) return NULL;  
     queue<GraphNode*> q;  
     q.push(node);  
     MAP map;  
     map[node] = new GraphNode(node->label);  
     while (!q.empty()) {  
       GraphNode *oriNode = q.front();   
       q.pop();  
       GraphNode *newNode = map[oriNode];  
       for (int i = 0; i < oriNode->neighbors.size(); ++i) {  
         GraphNode *oriNeighbor = oriNode->neighbors[i];  
         if (map.find(oriNeighbor) != map.end()) {  
           newNode->neighbors.push_back(map[oriNeighbor]); // already visited!不再加入队列中  
           continue;  
         }  
         GraphNode *newNeighbor = new GraphNode(oriNeighbor->label);  
         newNode->neighbors.push_back(newNeighbor);  
         map[oriNeighbor] = newNeighbor; // set up hash-map  
         q.push(oriNeighbor); // push for next visit  
       }  
     }  
     return map[node];  
   }  
 };