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

1. First node is labeled as `0`. Connect node `0`to both nodes `1`and `2`.
2. Second node is labeled as `1`. Connect node `1`to node `2`.
3. 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
/ \
\_/
``````

Thoughts:

1. BFS/DFS + node mapping

Code (BFS)

``````/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
*     int label;
*     vector<UndirectedGraphNode *> neighbors;
*     UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
// mp maps original node to the copy node
unordered_map <UndirectedGraphNode*, UndirectedGraphNode*> mp;

public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return node;
queue<UndirectedGraphNode* > q;
q.push(node);
while(!q.empty()){
// do two things: 1. update mapping record for NEIGH node 2. copy neighbor for the current node
UndirectedGraphNode * cur = q.front(); q.pop();
for(auto neigh : cur->neighbors){
if(mp.find(neigh) == mp.end()){
UndirectedGraphNode* cp_node = new UndirectedGraphNode(neigh->label);
mp[neigh] = cp_node;
q.push(neigh);
}
// copy cur neighbors
mp[cur] -> neighbors.push_back(mp[neigh]);
}
}

}

};
``````

Code (DFS)

``````/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
*     int label;
*     vector<UndirectedGraphNode *> neighbors;
*     UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
unordered_map <UndirectedGraphNode*, UndirectedGraphNode*> mp;
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return node;
if(mp.find(node) == mp.end()){
UndirectedGraphNode * head = new UndirectedGraphNode(node->label);
for(auto neigh: node->neighbors){
mp[node]-> neighbors.push_back(cloneGraph(neigh));

}
}

return mp[node];
}

};
``````

Special Thanks jianchaolifighter's solution