LeetCode

Clone Graph

2014.2.25 22:15

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:

Solution:

　　The target of this problem is to make a deep copy of a graph, represented by nodes and pointers. Note that yo're only given one of the nodes as entry to the graph. It would be natural to use BFS to exploit the graph. To distinguish the nodes, we'll need hashing with <unordered_map> or <map>.

　　Two tips for this problem:

　　　　1. self-loop is possible.

　　　　2. multigraph is possible.

　　With only one entry, you can restore only one connected component, so you may suppose the graph has exactly one connected component.

　　Time complexity is proportional to number of edges, while space complexity to number of vertices.

Accepted code:

 1 // 5CE, 2WA, 1AC, serialize first, deserialize later.
 2 #include <queue>
 3 #include <vector>
 4 #include <unordered_map>
 5 using namespace std;
 6 /**
 7  * Definition for undirected graph.
 8  * struct UndirectedGraphNode {
 9  *     int label;
10  *     vector<UndirectedGraphNode *> neighbors;
11  *     UndirectedGraphNode(int x) : label(x) {};
12  * };
13  */
14 class Solution {
15 public:
16     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
17         if (node == nullptr) {
18             return nullptr;
19         }
20         
21         UndirectedGraphNode *cur, *nei;
22         int i, j;
23         int nc;
24         int ix, iy;
25         int nsize;
26         
27         nc = 0;
28         qq.push(node);
29         while (!qq.empty()) {
30             cur = qq.front();
31             qq.pop();
32             if (um.find(cur) == um.end()) {
33                 um[cur] = nc++;
34                 graph.push_back(vector<int>());
35                 labels.push_back(cur->label);
36                 nodes_checked.push_back(false);
37             }
38             ix = um[cur];
39             if (nodes_checked[ix]) {
40                 continue;
41             }
42             nsize = (int)cur->neighbors.size();
43             for (i = 0; i < nsize; ++i) {
44                 nei = cur->neighbors[i];
45                 if (um.find(nei) == um.end()) {
46                     um[nei] = nc++;
47                     labels.push_back(nei->label);
48                     graph.push_back(vector<int>());
49                     nodes_checked.push_back(false);
50                 }
51                 iy = um[nei];
52                 if (!nodes_checked[iy]) {
53                     qq.push(nei);
54                 }
55                 graph[ix].push_back(iy);
56             }
57             nodes_checked[ix] = true;
58         }
59         
60         new_nodes.clear();
61         for (i = 0; i < nc; ++i) {
62             new_nodes.push_back(new UndirectedGraphNode(labels[i]));
63         }
64         for (i = 0; i < nc; ++i) {
65             nsize = (int)graph[i].size();
66             for (j = 0; j < nsize; ++j) {
67                 new_nodes[i]->neighbors.push_back(new_nodes[graph[i][j]]);
68             }
69         }
70         cur = new_nodes[0];
71         while (!qq.empty()) {
72             qq.pop();
73         }
74         um.clear();
75         new_nodes.clear();
76         for (i = 0; i < (int)graph.size(); ++i) {
77             graph[i].clear();
78         }
79         graph.clear();
80         labels.clear();
81         nodes_checked.clear();
82         
83         return cur;
84     }
85 private:
86     queue<UndirectedGraphNode *> qq;
87     unordered_map<UndirectedGraphNode *, int> um;
88     vector<int> labels;
89     vector<bool> nodes_checked;
90     vector<UndirectedGraphNode *> new_nodes;
91     vector<vector<int> > graph;
92 };