-
Notifications
You must be signed in to change notification settings - Fork 0
/
clone-graph(AC).cpp
92 lines (88 loc) · 1.99 KB
/
clone-graph(AC).cpp
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 5CE, 2WA, 1AC, serialize first, deserialize later.
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == nullptr) {
return nullptr;
}
UndirectedGraphNode *cur, *nei;
int i, j;
int nc;
int ix, iy;
int nsize;
nc = 0;
qq.push(node);
while (!qq.empty()) {
cur = qq.front();
qq.pop();
if (um.find(cur) == um.end()) {
um[cur] = nc++;
graph.push_back(vector<int>());
labels.push_back(cur->label);
nodes_checked.push_back(false);
}
ix = um[cur];
if (nodes_checked[ix]) {
continue;
}
nsize = (int)cur->neighbors.size();
for (i = 0; i < nsize; ++i) {
nei = cur->neighbors[i];
if (um.find(nei) == um.end()) {
um[nei] = nc++;
labels.push_back(nei->label);
graph.push_back(vector<int>());
nodes_checked.push_back(false);
}
iy = um[nei];
if (!nodes_checked[iy]) {
qq.push(nei);
}
graph[ix].push_back(iy);
}
nodes_checked[ix] = true;
}
new_nodes.clear();
for (i = 0; i < nc; ++i) {
new_nodes.push_back(new UndirectedGraphNode(labels[i]));
}
for (i = 0; i < nc; ++i) {
nsize = (int)graph[i].size();
for (j = 0; j < nsize; ++j) {
new_nodes[i]->neighbors.push_back(new_nodes[graph[i][j]]);
}
}
cur = new_nodes[0];
while (!qq.empty()) {
qq.pop();
}
um.clear();
new_nodes.clear();
for (i = 0; i < (int)graph.size(); ++i) {
graph[i].clear();
}
graph.clear();
labels.clear();
nodes_checked.clear();
return cur;
}
private:
queue<UndirectedGraphNode *> qq;
unordered_map<UndirectedGraphNode *, int> um;
vector<int> labels;
vector<bool> nodes_checked;
vector<UndirectedGraphNode *> new_nodes;
vector<vector<int> > graph;
};