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         / \         \_/

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         unordered_map
        
          map;13         if (node == nullptr) {14             return nullptr;15         }16         return clone(node, map);17     }18 private:19     UndirectedGraphNode *clone(UndirectedGraphNode *node, 20             unordered_map
         
           &map) {21         if (map.find(node) != map.end()) {22             return map[node];23         } 24         UndirectedGraphNode *new_node = new UndirectedGraphNode(node->label);25         map[node] = new_node;26         for (auto n : node->neighbors) {27             new_node->neighbors.push_back(clone(n, map));28         }29         return new_node;30     }31 };
         
        
       

借助hash表