Clone Graph
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 node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
--------------------------- thinking ------------------------------------------------------
1. we need to use a hash map to record the corresponding node and its clone
2. in fact, we don't need a set to record the visited information anymore, hash map can fulfill this function, since we only need to add the new node that been cloned to the queue instead of checking if a node is visited or not
3. the speed of using DFS and BFS
------------------------------- codes ------------------------------------------------------
/**
* 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;
vector<UndirectedGraphNode*> stack;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
unordered_set<UndirectedGraphNode*> visited;
UndirectedGraphNode *out = new UndirectedGraphNode(node->label);
map[node] = out;
stack.push_back(node);
while(stack.size()) {
UndirectedGraphNode *cur = stack.back();
stack.pop_back();
//every node in the stack should already has a new copy
UndirectedGraphNode *cur_new = map[cur];
if (visited.find(cur) == visited.end()) {
for (int i = 0; i < cur->neighbors.size(); i++) {
if (map[cur->neighbors[i]]) {
cur_new->neighbors.push_back(map[cur->neighbors[i]]);
} else {
UndirectedGraphNode * node_new = new UndirectedGraphNode(cur->neighbors[i]->label);
cur_new->neighbors.push_back(node_new);
map[cur->neighbors[i]] = node_new;
}
if (visited.find(cur->neighbors[i]) == visited.end()) {
stack.push_back(cur->neighbors[i]);
}
}
visited.insert(cur);
}
}
return out;
}
};
--------------------------------------- codes ---------------------------------------------------
/**
* 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;
vector<UndirectedGraphNode*> stack;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> map;
UndirectedGraphNode *out = new UndirectedGraphNode(node->label);
map[node] = out;
stack.push_back(node);
while(stack.size()) {
UndirectedGraphNode *cur = stack.back();
stack.pop_back();
//every node in the stack should already has a new copy
UndirectedGraphNode *cur_new = map[cur];
//if (visited.find(cur) == visited.end()) {
for (int i = 0; i < cur->neighbors.size(); i++) {
if (map[cur->neighbors[i]]) {
cur_new->neighbors.push_back(map[cur->neighbors[i]]);
} else {
UndirectedGraphNode * node_new = new UndirectedGraphNode(cur->neighbors[i]->label);
cur_new->neighbors.push_back(node_new);
map[cur->neighbors[i]] = node_new;
stack.push_back(cur->neighbors[i]);
}
}
//visited.insert(cur);
//}
}
return out;
}
};
No comments:
Post a Comment