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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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，也可以BFS，复制则是一个map的问题（label唯一）。map中的key对应原节点，value对应新建的节点。

先来看BFS的。BFS必然用到一个队列q，然后一个while循环，退出的条件是队列q为空。循环内，首先取出队列的头部节点tmp，接下来判断tmp是否已经出现在map当中。如果map中没有，则新建一个节点，同时用map关联tmp节点和新建的节点。这个判断很重要，最开始我没有这个判断，就会错，以题干的例子说明为什么错。感谢的指导。

首先访问节点0，新建节点0`，map<0, 0`>。然后0的第一个邻居节点1，这个节点在map中找不到，所以新建节点1`，关联map<1,1`>，节点1进入队列q，0`邻居节点1`。同理接下来0的第二个邻居节点2完成相同的操作。以上都是第一次while()的过程。接下来再判断while的条件，q非空，取q头部节点1，如果没有此时没有前述的判断，则又会新建一个节点1``，这个节点与map(1)对应的1`只是label一样，确是两个完全不同的节点。本来1`的邻居节点是2`，这样一次while之后其实是1``的邻居节点是2`，当然最后的结果就是错的。所以上面的判断其实是判断是否已经建立了此次访问的节点。

根据BFS，接下来是寻找节点的邻居节点。寻找邻居节点，当然还得要用到前面的那个判断思路，这样才能避免如果新建了一个节点1`，不至于又去建立一个全新的1``了。

 

再来看DFS。因为图没有完全独立的部分，所以只需对第一个节点进行深搜即可，只要一次神搜完成而不用判断是否有其余节点没有访问到。这里还是的用到前述的那个判断条件，道理类似。如果map中没有，那么就新建一个节点，同时关联原节点和新建的节点，在对原节点进行一次递归的DFS，返回的结果就是邻居节点；如果map中存在，说明节点已经被关联过了，只需返回关联的那个节点即可。

题解：

BFS

/** * Definition for undirected graph. * struct UndirectedGraphNode { *     int label; *     vector
      
        neighbors; *     UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution {public:    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {        if(node==NULL)            return NULL;        unordered_map
       
         map;        queue
        
          q;        q.push(node);        while(!q.empty()) {            UndirectedGraphNode *tmp = q.front();            q.pop();            if(map.find(tmp)==map.end()) {                UndirectedGraphNode *newnode = new UndirectedGraphNode(tmp->label);                map[tmp] = newnode;            }            for(int i=0;i
         
          neighbors.size();i++) {                UndirectedGraphNode *neighbor = tmp->neighbors[i];                if(map.find(neighbor)==map.end()) {                    UndirectedGraphNode *newneighbor = new UndirectedGraphNode(neighbor->label);                    map[neighbor] = newneighbor;                    q.push(neighbor);                }                map[tmp]->neighbors.push_back(map[neighbor]);            }        }        return map[node];    }};
         
        
       
      

DFS

/** * Definition for undirected graph. * struct UndirectedGraphNode { *     int label; *     vector
      
        neighbors; *     UndirectedGraphNode(int x) : label(x) {}; * }; */class Solution {public:    unordered_map
       
         map;    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {        if(node==NULL)            return NULL;        if(map.find(node)==map.end()) {            UndirectedGraphNode *newnode = new UndirectedGraphNode(node->label);            map[node] = newnode;            for(int i=0;i
        
         neighbors.size();i++)                newnode->neighbors.push_back(cloneGraph(node->neighbors[i]));            return newnode;        }        else            return map[node];    }};