# 133. Clone Graph

Difficulty: Medium

Frequency: N/A

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
/ \
\_/```

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```/**
* 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) return NULL;
UndirectedGraphNode *p1 = node;
UndirectedGraphNode *p2 = new UndirectedGraphNode(node->label);
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m;
queue<UndirectedGraphNode*> q;
q.push(node);
m[node] = p2;
while (!q.empty()) {
p1 = q.front();
p2 = m[p1];
q.pop();
for (int i = 0; i < p1->neighbors.size(); i++) {
UndirectedGraphNode *nb = p1->neighbors[i];
if (m.count(nb)) {
p2->neighbors.push_back(m[nb]);
} else {
UndirectedGraphNode *tmp = new UndirectedGraphNode(nb->label);
p2->neighbors.push_back(tmp);
m[nb] = tmp;
q.push(nb);
}
}
}
return m[node];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn: