forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcloneGraph.cpp
More file actions
83 lines (75 loc) · 2.69 KB
/
cloneGraph.cpp
File metadata and controls
83 lines (75 loc) · 2.69 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
// Source : https://oj.leetcode.com/problems/clone-graph/
// Author : Hao Chen
// Date : 2014-10-12
/**********************************************************************************
*
* Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
*
* OJ's undirected graph serialization:
*
* Nodes are labeled uniquely.
*
* We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
*
* As an example, consider the serialized graph {0,1,2#1,2#2,2}.
*
* The graph has a total of three nodes, and therefore contains three parts as separated by #.
*
* First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
* Second node is labeled as 1. Connect node 1 to node 2.
* Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
*
* Visually, the graph looks like the following:
*
* 1
* / \
* / \
* 0 --- 2
* / \
* \_/
*
*
**********************************************************************************/
/**
* 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 == NULL) return NULL;
//create a map, key is source node, value is clone node.
map<UndirectedGraphNode*, UndirectedGraphNode*> cloneMap;
//using queue for breadth first search
queue<UndirectedGraphNode*> q;
q.push(node);
//clone the root
UndirectedGraphNode* cloneNode = new UndirectedGraphNode(node->label);
cloneMap[node] = cloneNode;
//breadth first search
while(!q.empty()){
UndirectedGraphNode* n = q.front();
q.pop();
//for each neighbors
for(int i=0; i<n->neighbors.size(); i++){
UndirectedGraphNode* neighbor= n->neighbors[i];
//not existed in cloneMap
if (cloneMap.find(neighbor)==cloneMap.end()){
//clone a node
UndirectedGraphNode* newNode = new UndirectedGraphNode(neighbor->label);
cloneMap[n]->neighbors.push_back(newNode);
cloneMap[neighbor] = newNode;
//put the neighbors into the queue
q.push(neighbor);
}else{
cloneMap[n]->neighbors.push_back(cloneMap[neighbor]);
}
}
}
return cloneNode;
}
};