/
9_CloneAGraph.cpp
59 lines (52 loc) · 1.39 KB
/
9_CloneAGraph.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
/*
Question : https://leetcode.com/problems/clone-graph/
Approach : Traverse each non-visited vertices/nodes of a graph and clone the nodes one by one. Also clone the neighbors from the original graph.
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* bfs(Node* src){
queue<Node*> q;
q.push(src);
Node* n = new Node(src->val);
map<Node*, Node*> mp; //used for tracking the visited nodes
mp[src] = n;
while(!q.empty()){
Node *u = q.front();
q.pop();
vector<Node*> v = u->neighbors;
int n = v.size();
for(int i = 0; i < n; i++){
if(mp[v[i]] == NULL){
Node* node = new Node(v[i]->val);
q.push(v[i]);
mp[v[i]] = node;
}
mp[u]->neighbors.push_back(mp[v[i]]);
}
}
return mp[src];
}
Node* cloneGraph(Node* node) {
if(node == NULL)
return NULL;
return bfs(node);
}
};