《Cracking the Coding Interview》——第13章：C和C++—

《Cracking the Coding Interview》——第13章：C和C++——题目7

2014-04-25 20:18

题目：给定一个Node结构体，其中包含数据成员和两个Node*指针指向其他两个Node结构(还不如直接说这是个图呢)。给你一个Node指针作为参数，请做一份深拷贝作为结果返回。

解法：BFS搞定，需要检测重复节点以防止死循环，用一个哈希表可以做大。这样肯定只能找出一个完整的连通分量，其他连通分量的节点是无法检测到的。下面的代码其实是我在做leetcode时写的。

代码：

 1 // 13.7 Given a pointer to a Node strcut, return a deep copy of whatever you can find with it.
 2 // Answer:
 3 //    The following code is actually my solution to the leetcode problem, Clone Graph.
 4 //    They are different problems, but almost the same idea of BFS, mapping and deep copy.
 5 #include <queue>
 6 #include <vector>
 7 #include <unordered_map>
 8 using namespace std;
 9 /**
10  * Definition for undirected graph.
11  * struct UndirectedGraphNode {
12  *     int label;
13  *     vector<UndirectedGraphNode *> neighbors;
14  *     UndirectedGraphNode(int x) : label(x) {};
15  * };
16  */
17 class Solution {
18 public:
19     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
20         if (node == nullptr) {
21             return nullptr;
22         }
23         
24         UndirectedGraphNode *cur, *nei;
25         int i, j;
26         int nc;
27         int ix, iy;
28         int nsize;
29         
30         nc = 0;
31         qq.push(node);
32         while (!qq.empty()) {
33             cur = qq.front();
34             qq.pop();
35             if (um.find(cur) == um.end()) {
36                 um[cur] = nc++;
37                 graph.push_back(vector<int>());
38                 labels.push_back(cur->label);
39                 nodes_checked.push_back(false);
40             }
41             ix = um[cur];
42             if (nodes_checked[ix]) {
43                 continue;
44             }
45             nsize = (int)cur->neighbors.size();
46             for (i = 0; i < nsize; ++i) {
47                 nei = cur->neighbors[i];
48                 if (um.find(nei) == um.end()) {
49                     um[nei] = nc++;
50                     labels.push_back(nei->label);
51                     graph.push_back(vector<int>());
52                     nodes_checked.push_back(false);
53                 }
54                 iy = um[nei];
55                 if (!nodes_checked[iy]) {
56                     qq.push(nei);
57                 }
58                 graph[ix].push_back(iy);
59             }
60             nodes_checked[ix] = true;
61         }
62         
63         new_nodes.clear();
64         for (i = 0; i < nc; ++i) {
65             new_nodes.push_back(new UndirectedGraphNode(labels[i]));
66         }
67         for (i = 0; i < nc; ++i) {
68             nsize = (int)graph[i].size();
69             for (j = 0; j < nsize; ++j) {
70                 new_nodes[i]->neighbors.push_back(new_nodes[graph[i][j]]);
71             }
72         }
73         cur = new_nodes[0];
74         while (!qq.empty()) {
75             qq.pop();
76         }
77         um.clear();
78         new_nodes.clear();
79         for (i = 0; i < (int)graph.size(); ++i) {
80             graph[i].clear();
81         }
82         graph.clear();
83         labels.clear();
84         nodes_checked.clear();
85         
86         return cur;
87     }
88 private:
89     queue<UndirectedGraphNode *> qq;
90     unordered_map<UndirectedGraphNode *, int> um;
91     vector<int> labels;
92     vector<bool> nodes_checked;
93     vector<UndirectedGraphNode *> new_nodes;
94     vector<vector<int> > graph;
95 };