forked from fanfank/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
clone-graph.cpp
39 lines (37 loc) · 1.23 KB
/
clone-graph.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
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
typedef UndirectedGraphNode UG;
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL)
return NULL;
map<UG*, UG*> m;
queue<UG*> q;
UG *newNode = new UG(node->label);
q.push(node);
m[node] = newNode;
while(!q.empty()) {
UG *original = q.front(), *current = m[original];
q.pop();
for(vector<UG*>::iterator neighbor = original->neighbors.begin(); neighbor != original->neighbors.end(); ++neighbor) {
map<UG*, UG*>::iterator p = m.find(*neighbor);
if(p == m.end()) {
UG *tmp = new UG((*neighbor)->label);
m[*neighbor] = tmp;
q.push(*neighbor);
current->neighbors.push_back(tmp);
} else {
current->neighbors.push_back(p->second);
}
}
}
return newNode;
}
};