leetcode[133]Clone Graph

3647 단어 LeetCode
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  # .
  • First node is labeled as  0 . Connect node  0  to both nodes  1  and  2 .
  • Second node is labeled as  1 . Connect node  1  to node  2 .
  • 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
    
             / \
    
             \_/
    /**
    
     * Definition for undirected graph.
    
     * struct UndirectedGraphNode {
    
     *     int label;
    
     *     vector<UndirectedGraphNode *> neighbors;
    
     *     UndirectedGraphNode(int x) : label(x) {};
    
     * };
    
     */
    
    class Solution {
    
    public:
    
    UndirectedGraphNode * clone(unordered_map<int, UndirectedGraphNode *> &map1,UndirectedGraphNode *node)
    
    {
    
        if(map1.count(node->label))
    
            return map1[node->label];
    
        UndirectedGraphNode *new_node=new UndirectedGraphNode(node->label);
    
        map1[new_node->label]=new_node;
    
        for(auto &nod :node->neighbors)
    
        {
    
            new_node->neighbors.push_back(clone(map1,nod));
    
        }
    
        return new_node;
    
    }
    
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    
            if(node==NULL)return node;
    
            unordered_map<int, UndirectedGraphNode *> map1;
    
            return clone(map1,node);
    
        }
    
    };

    좋은 웹페이지 즐겨찾기