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掉的思想已经很接近了,被他们又是说这说那的绕进去了,就是一个单调栈,栈中元素的纵坐标严格降低,并且栈中顶部两点之间斜率的绝对值要小于栈...

    triplebee
  • Leetcode 77 Combinations

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

    triplebee
  • HDU2066

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

    triplebee
  • 「小程序JAVA实战」java的聚合项目搭建(30)

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

    IT故事会
  • [UWP 自定义控件]了解模板化控件(9):UI指南

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

    dino.c
  • Vim高手,从来不用鼠标2——替换、撤销、缩进、查找

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

    编程三分钟
  • 线性代数--MIT18.06(十二)

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

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

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

    hrscy
  • 设计模式之建造者模式

    tanoak
  • WCF IIS 部署错误处理

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

    用户1637609

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动