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

Subscribe to see which companies asked this question

dfs，用map记录克隆过的点，easy

```/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
*     int label;
*     vector<UndirectedGraphNode *> neighbors;
*     UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode* dfs(UndirectedGraphNode* now, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>& mp)
{
if(mp.find(now) != mp.end()) return mp[now];
UndirectedGraphNode* clone = new UndirectedGraphNode(now->label);
mp[now] = clone;
for(int i=0;i < now->neighbors.size(); i++)
{
UndirectedGraphNode* t = dfs(now->neighbors[i],mp);
if(t) clone->neighbors.push_back(t);
}
return clone;
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return NULL;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
return dfs(node, mp);
}
};```

0 条评论

• ### HDU5033

真蠢，和网络赛的时候我WA掉的思想已经很接近了，被他们又是说这说那的绕进去了，就是一个单调栈，栈中元素的纵坐标严格降低，并且栈中顶部两点之间斜率的绝对值要小于栈...

• ### Leetcode 77 Combinations

Given two integers n and k, return all possible combinations of k numbers out o...

• ### HDU2066

神坑的题目 思路就是枚举起点，迪杰斯特拉求最短路径，再枚举终点（如果起点终点一起枚举可能会超时，也能勉强扯上动态规划的思想吧），求最短路径。 如果剪枝可以加一个...

• ### 「小程序JAVA实战」java的聚合项目搭建（30）

PS：其实不光是api和web层还有可能有什么文件管理层，权限层等等。都可以通过一层一层调用的方式不断的进行扩张，减少代码很方便。

• ### [UWP 自定义控件]了解模板化控件(9)：UI指南

TemplateSettings提供一组只读属性，用于在新建ControlTemplate时使用这些约定的属性。

• ### Vim高手，从来不用鼠标2——替换、撤销、缩进、查找

“ 查找和替换是编辑器中最常用的功能之一，这一次就让我们敲击几下键盘，完成查找与替换吧! ——编程三分钟”

• ### 线性代数--MIT18.06(十二)

在之前的课程中，列举了很多的矩阵，实际上它们都来自实际问题，而不是简简单单随便想出来的，这些矩阵都可以描述实际问题的拓扑结构，我们在处理这些实际问题时需要搞清楚...

• ### 记录网站诞生过程-使用hexo+github pages

此博客记录了搭建网站的详细过程,以及建站过程中遇到的一些坑。博客介绍了安装homebrew,nodejs,hexo,域名注册,github设置,DNS解析等过程...

• ### WCF IIS 部署错误处理

做Web接口，原来一直用Web Service的，但是.Net 3.5后，Web Service变成了WCF。代码的编写上，把WebMethod特性改成了Ope...