1 /**
 2  * Definition for undirected graph.
 3  * struct UndirectedGraphNode {
 4  *     int label;
 5  *     vector<UndirectedGraphNode *> neighbors;
 6  *     UndirectedGraphNode(int x) : label(x) {};
 7  * };
 8  */
 9 class Solution {
10 public:
11     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
12         if(node==NULL)
13         return NULL;
14         unordered_set<int> visted;//保存访问过的节点label
15         unordered_map<int,UndirectedGraphNode*> pointMap;//保存节点的新地址
16         queue<UndirectedGraphNode*> qu;
17         qu.push(node);
18         UndirectedGraphNode *newNode=new UndirectedGraphNode(node->label);
19         UndirectedGraphNode *startNode=newNode;
20         pointMap.insert(make_pair(node->label,newNode));
21         while(!qu.empty())
22         {
23             UndirectedGraphNode *oldNode=qu.front();
24             newNode=pointMap.find(oldNode->label)->second;
25             qu.pop();
26             for(vector<UndirectedGraphNode*>::iterator iter=oldNode->neighbors.begin();iter!=oldNode->neighbors.end();iter++)
27             {
28                 
29                 if(visted.find((*iter)->label)==visted.end()&&(pointMap.find((*iter)->label)==pointMap.end()))
30                 {
31                    UndirectedGraphNode *q=new UndirectedGraphNode((*iter)->label);
32                    pointMap.insert(make_pair((*iter)->label,q));
33                     qu.push(*iter);
34                     newNode->neighbors.push_back(q);
35                 }
36                 else
37                 {
38                     newNode->neighbors.push_back(pointMap.find((*iter)->label)->second);
39                 }
40             }
41             visted.insert(oldNode->label);
42 
43         }
44         return startNode;
45         
46         
47     }
48 };