-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathclone-graph.cpp
More file actions
123 lines (98 loc) · 3.05 KB
/
clone-graph.cpp
File metadata and controls
123 lines (98 loc) · 3.05 KB
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <queue>
#include <unordered_map>
#include "leetcode.h"
class SolutionV2 {
public:
unordered_set<int> visited;
unordered_map<int, UndirectedGraphNode *> nodes;
UndirectedGraphNode *dfs(UndirectedGraphNode *node) {
if (node == NULL) return NULL;
if ( visited.find(node->label) != visited.end() )
return nodes[node->label];
auto &node_clone = nodes[node->label];
if (!node_clone)
node_clone = new UndirectedGraphNode(node->label);
for (UndirectedGraphNode *nbr : node->neighbors) {
auto &nbr_clone = nodes[nbr->label];
if (!nbr_clone) {
nbr_clone = dfs(nbr);
}
node_clone->neighbors.push_back(nbr_clone);
}
visited.insert(node->label);
return node_clone;
}
UndirectedGraphNode *bfs(UndirectedGraphNode *node) {
if (node == NULL) return NULL;
nodes[node->label] = new UndirectedGraphNode(node->label);
queue<UndirectedGraphNode *> q;
q.push(node);
while (!q.empty()) {
UndirectedGraphNode *nd = q.front();
q.pop();
if (visited.find(nd->label) != visited.end()) {
continue;
}
auto &node_clone = nodes[nd->label];
if (!node_clone)
node_clone = new UndirectedGraphNode(nd->label);
visited.insert(nd->label);
for (UndirectedGraphNode *nbr : nd->neighbors) {
auto &nbr_clone = nodes[nbr->label];
if (!nbr_clone) {
nbr_clone = new UndirectedGraphNode(nbr->label);
}
node_clone->neighbors.push_back(nbr_clone);
if (visited.find(nbr->label) == visited.end()) {
q.push(nbr);
}
}
}
return nodes[node->label];
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
visited.clear();
nodes.clear();
return bfs(node);
}
};
class Solution {
std::unordered_map<int, UndirectedGraphNode *> clone;
std::unordered_set<int> visited;
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == NULL) return NULL;
std::queue<UndirectedGraphNode *> myqueue;
myqueue.push(node);
while ( !myqueue.empty() ) {
UndirectedGraphNode *p = myqueue.front();
myqueue.pop();
// already visited this node
if ( visited.find(p->label) != visited.end() )
continue;
visited.insert(p->label);
UndirectedGraphNode *cur = clone[p->label];
if (cur == NULL)
cur = clone[p->label] = new UndirectedGraphNode(p->label);
for (auto nbr : p->neighbors) {
UndirectedGraphNode *clone_nbr = clone[nbr->label];
if (clone_nbr == NULL) {
clone_nbr = clone[nbr->label] = new UndirectedGraphNode(nbr->label);
}
if ( visited.find(nbr->label) == visited.end() )
myqueue.push(nbr);
cur->neighbors.push_back(clone_nbr);
}
} // while
return clone[node->label];
}
};
int main() {
Solution sol;
string graph = "0,1,2#1,2#2,2";
UndirectedGraphNode *node = deserialize_graph(graph);
serialize_graph(cout, node);
auto nn = sol.cloneGraph(node);
serialize_graph(cout, nn);
return 0;
}