EEPW论坛

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.

Nodes are labeled uniquely.

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 as0. Connect node0to both nodes1and2.

2. Second node is labeled as1. Connect node1to node2.

3. Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.

Visually, the graph looks like the following:

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

题意:

克隆一个无向图，途中的每个节点包含一个标签及其邻居的列表

Oj对于无向图的序列化；

节点的标签是唯一的。

我们使用#作为节点的分割符，使用逗号，作为节点标签以及每个邻居之间的分割符；

例如，考虑序列化图0，1，2#1，2#2,2

上图包含三个几点，

第一个节点标签为0， 节点0与节点1、2相连；

第二个节点标签为1，节点1与节点2相连；

第三个节点为2，节点2与节点2相连，形成了一个环；

这道题主要是数据结构的应用吧，用一个队列存放途中还未被访问的节点，
用一个map存放克隆的新节点。对于队列中的节点，访问其邻居节点，如果该
邻居已经被克隆，那么只需要维护克隆节点之间的邻居关系即可，如果该邻居
尚未被克隆，那么需要new一个新节点作为它的克隆，并维护克隆后的邻居关系；

1. class Solution {  

2. public:  

3.     

4.     map<int,UndirectedGraphNode*> record;  

5.     UndirectedGraphNode *clone(UndirectedGraphNode *node) {  

6.         UndirectedGraphNode *ngraph,*p;  

7.         map<int,UndirectedGraphNode*>::iterator iter;  

8.         p=node;  

9.         iter=record.find(p->label);  

10.         if(iter!=record.end())  

11.             return iter->second;  

12.         ngraph=new UndirectedGraphNode(p->label);  

13.         record.insert(map<int,UndirectedGraphNode*>::value_type(p->label,ngraph));  

14.         for(int i=0;i<p->neighbors.size();i++){  

15.             ngraph->neighbors.push_back(clone(p->neighbors[i]));  

16.         }  

17.         return ngraph;  

18.     }  

19.     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node){  

20.         UndirectedGraphNode *ngraph;  

21.         if(node==NULL)  

22.             return NULL;  

23.         record.clear();  

24.         ngraph=clone(node);  

25.         return ngraph;  

26.     }  

27. };