dfs or bfs
//dfs
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> nodeMap;
return cloneGraph(node,nodeMap);
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node,unordered_map<
UndirectedGraphNode *,UndirectedGraphNode *>& nodeMap ){
if(!node) return NULL;
if(nodeMap.count(node) > 0)
return nodeMap[node];
UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
nodeMap[node] = newNode;
for(auto it = (node->neighbors).begin(); it != (node->neighbors).end(); ++it){
(newNode->neighbors).push_back( cloneGraph(*it,nodeMap) );
}
return newNode;
}
};
//bfs
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return NULL;
UndirectedGraphNode *clnode=new UndirectedGraphNode(node->label);
unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> map;
map[node]=clnode;
queue<UndirectedGraphNode *> que;
que.push(node);
while(!que.empty()){
UndirectedGraphNode *current=que.front();que.pop();
for(auto it=current->neighbors.begin();it!=current->neighbors.end();it++){
if(map.find(*it)==map.end()){
UndirectedGraphNode *neibor=new UndirectedGraphNode((*it)->label);
map[*it]=neibor;
map[current]->neighbors.push_back(neibor);
que.push(*it);
}else{
map[current]->neighbors.push_back(map[*it]);
}
}
}
return clnode;
}
No comments:
Post a Comment