# 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.