这题的思路就是建一个old graph到新的graph点的对应map，queue表示还未访问过的old graph的点的队列，如果queue的front的点的neighbors vector里有未访问的点就添加到队列里。

1 /** 2  * Definition for undirected graph. 3  * struct UndirectedGraphNode { 4  *     int label; 5  *     vector
     
       neighbors; 6  *     UndirectedGraphNode(int x) : label(x) {}; 7  * }; 8  */ 9 class Solution {10 public:11     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {12         // IMPORTANT: Please reset any member data you declared, as13         // the same Solution instance will be reused for each test case.14         if (node == NULL) return NULL;15         map
      
        S;16         UndirectedGraphNode *res = new UndirectedGraphNode(node->label);17         S[node] = res;18         queue
       
         que;19         que.push(node);20         while (!que.empty()) {21             UndirectedGraphNode *t = que.front();22             que.pop();23             for (int i = 0; i < t->neighbors.size(); i++) {24                 UndirectedGraphNode *nei = t->neighbors[i];25                 if (S.count(nei)) S[t]->neighbors.push_back(S[nei]);26                 else {27                     que.push(nei);28                     UndirectedGraphNode *tmp = new UndirectedGraphNode(nei->label);29                     S[nei] = tmp;30                     S[t]->neighbors.push_back(tmp);31                 }32             }33         }34         return res;35     }36 };
       
      
     

 C#

1 /** 2  * Definition for undirected graph. 3  * public class UndirectedGraphNode { 4  *     public int label; 5  *     public IList
      
        neighbors; 6  *     public UndirectedGraphNode(int x) { label = x; neighbors = new List
       
        (); } 7  * }; 8  */ 9 public class Solution {10     public UndirectedGraphNode CloneGraph(UndirectedGraphNode node) {11         if (node == null) return null;12         Dictionary
        
          S = new Dictionary
         
          ();13         UndirectedGraphNode ans = new UndirectedGraphNode(node.label);14         S.Add(node, ans);15         Queue
          
            que = new Queue
           
            ();16 que.Enqueue(node);17 while (que.Count != 0) {18 UndirectedGraphNode peek = que.Peek();19 que.Dequeue();20 for (int i = 0; i < peek.neighbors.Count; i++) {21 UndirectedGraphNode nei = peek.neighbors[i];22 if (S.ContainsKey(nei)) S[peek].neighbors.Add(S[nei]);23 else {24 que.Enqueue(nei);25 UndirectedGraphNode tmp = new UndirectedGraphNode(nei.label);26 S.Add(nei, tmp);27 S[peek].neighbors.Add(tmp);28 }29 }30 }31 return ans;32 }33 }