Description
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
The original problem is here.
The original code is here.
My Solution
I solve this problem in C++, as below:
/*
*Clone Graph
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<vector>
#include <unordered_set>
#include<string.h>
#include<stdlib.h>
/**
* 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;
map<UndirectedGraphNode*, UndirectedGraphNode*> copied;
clone(node, copied);
return copied[node];
}
UndirectedGraphNode *clone(UndirectedGraphNode *node, map<UndirectedGraphNode*, UndirectedGraphNode*> copied) {
if(node == NULL)
return NULL;
if(copied.find(node) != copied.end())
return copied[node];
UndirectedGraphNode * root = new UndirectedGraphNode(node->label);
vector<UndirectedGraphNode *> neighbors = node->neighbors;
copied[node] = root;
for(int i=0;i<neighbors.size(); i++){
UndirectedGraphNode * temp = neighbors[i];
UndirectedGraphNode * neighbor = cloneGraph(temp, copied);
root->neighbors.push_back(neighbor);
}
return root;
}
};
Note
To solve the problem, depth-first search was used. In order to avoid the node to be copied more than once, a map was also need.