133. Clone Graph

题目

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

解析

• 考察图的基本遍历方法，DFS/BFS
• 注意细节bug
• 运用unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash进行图的映射关系存储

// clone graphclass Solution_133 {// date 2017/12/29 10:01// date 2017/12/29 11:04public:    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {         unordered_map
    
      hash;        if (!node)        {            return node;        }        if (hash.find(node)!=hash.end()) //找到，关键字已经访问过        {            hash[node] = new UndirectedGraphNode(node->label);            for (auto iter: node->neighbors)            {                hash[node]->neighbors.push_back(cloneGraph(iter)); //递归DFS   //超时            }        }        return hash[node];    }    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) //BFS    {               if (!node)        {            return node;        }           unordered_map
     
       hash;        UndirectedGraphNode* head = new UndirectedGraphNode(node->label);        hash[node] = head;        queue
      
        que;        que.push(node);  //que.push(head); bug 花费1小时查找        while (!que.empty())        {            UndirectedGraphNode* q = que.front();            que.pop();            for (auto iter: q->neighbors)            {                if (!hash[iter]) //还没有访问                {                    UndirectedGraphNode* temp = new UndirectedGraphNode(iter->label);                    hash[iter] = temp;                    que.push(iter);                }                hash[q]->neighbors.push_back(hash[iter]); //将一个节点的邻接点关系记录下来            }                    }        return hash[node];    }};
      
     
    

题目来源