LintCode(137): 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 #.

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

这个题目和linked list with random pointer 遍历差不多，先复制点，在复制边，

复制点的时候用一个hash table来避免循环， 用一个queue来实现广度优先， 为了第二次链接边的时候减小复杂度，维护一个vector来记录每一次被push进去的顺序，这要更新边的时候只需要遍历这个vector就好了。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: /** * @param node: A undirected graph node * @return: A undirected graph node */ typedef UndirectedGraphNode n; UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { // write your code here if (!node) return node; vector<n*> seq; unordered_map<n*, n*> map; queue<n*> q; q.push(node); seq.push_back(node); map[node] = new n(node->label); while(!q.empty()){ n* tmp= q.front(); q.pop(); for (int i=0; i<tmp->neighbors.size(); i++){ n* sub=tmp->neighbors[i]; if (map.find(sub)!=map.end()) continue; map[sub] = new n(sub->label); q.push(sub); seq.push_back(sub); } } for (int i=0; i<seq.size(); i++){ n* tmp=seq[i]; for (int j=0; j<tmp->neighbors.size(); j++){ map[tmp]->neighbors.push_back(map[tmp->neighbors[j]]); } } return map[node]; } };