文档章节

133. Clone Graph

cofama
 cofama
发布于 2017/04/11 09:48
字数 534
阅读 4
收藏 0

原题链接

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.Nodes are labeled uniquely.

题目的意思是复制一个图,本质上就是复制节点信息,对于每一个旧节点都要new一个新节点,并且把label和邻居信息复制进去。遍历旧图中的所有节点是必需的,我用BFS和DFS各做了一遍。在图中可能有这么一种情况:A和B、C均相邻,那么无论是BFS还是DFS,A会经由B、C各遍历一次,这样就会创建两个新的A节点。重复创建新节点除了造成冗余,最重要是它会清除已有的节点信息。例如A已有一个对应的新节点A1,A1中已经复制了一部分A的邻居信息,这时从某个节点又遍历到A,又创建了一个新节点A2,此时A2中完全没有A的邻居信息,也就是A1中的信息被浪费了。为了确保新节点的唯一性,可以用bool数组记录每个旧节点是否都已有新节点,但问题是在遍历前不知道图中节点的个数,所以无法预先分配数组的大小。由此想到需要用一种不允许重复元素存在的容器,C++中的map符合这个要求,我们可以用旧节点作key,新节点作value,这样每个旧节点都绑定了唯一的新节点。题目中说到每个节点的label都是唯一的,所以用label做key也可以。

BFS:

/**
 * 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<int, UndirectedGraphNode *> m;
        m[node->label] = new UndirectedGraphNode(node->label);
        queue<UndirectedGraphNode *> q;
        q.push(node);
        
        UndirectedGraphNode *current;
        
        while(!q.empty()) {
            current = q.front();
            for(UndirectedGraphNode *x : current->neighbors) {
                if(m.find(x->label)==m.end()) {
                    m[x->label] = new UndirectedGraphNode(x->label);
                    q.push(x);
                }
                m[current->label]->neighbors.push_back(m[x->label]);
            }
            q.pop();
        }
        return m[node->label];
    }
};

DFS:

class Solution {
public:
    map<UndirectedGraphNode*, UndirectedGraphNode*> m;
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(node==NULL) return NULL;
        if(m.count(node) == 0) {
           m[node] = new UndirectedGraphNode(node->label);
           for (UndirectedGraphNode* x : node->neighbors) {
                m[node]->neighbors.push_back(cloneGraph(x));
           }
        }
        return m[node];
    }
};

© 著作权归作者所有

cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
私信 提问
FTP服务器

为了实现不同平台的文件共享,比如windows 和linux 。我们采用强大的文件共享工具FTP 1、首先安装FTP软件 yum install ftp.x8664 vsftpd.x8664 lftp.x86_64 2、在ftp的主配置文件中 /etc/vsf...

柳白子
2016/10/14
14
0
Bonobo Git Server 3.3 发布

Bonobo Git Server 3.3 发布,此版本更新内容如下: 新特性 Clone button for repositories in web management UI - latop2604 Support for custom title, logo, additional footer message......

oschina
2014/08/25
1K
1
克隆无向图 Clone Graph

问题: Clone an undirected graph. Each node in the graph contains a and a list of its . OJ's undirected graph serialization: Nodes are labeled uniquely. We use as a separator fo......

叶枫啦啦
2017/09/28
0
0
zabbix(二)——基本使用

step1:首次登陆zabbix #### 主选项卡: #### Administration:负责常规设置,用户验证,媒介设定相关设定 #### configuration:顾名思义,主要的配置都是通过此选项来设定 #### monitoring:...

异类深呼吸
2014/05/11
0
2
Zeppelin 0.5.5-incubating 发布,云计算管理和监控

Zeppelin 0.5.5-incubating 发布,此版本主要关注后端支持改进,稳定性改进,简化配置,有超过 60 位贡献者参与,提供新特性,改进和修复,解决了 90+ issues。 此版本后端支持: Apache Ign...

淡漠悠然
2015/11/20
751
0

没有更多内容

加载失败,请刷新页面

加载更多

0.01-Win10安装linux子系统

一、安装Debian子系统 -1、控制面板设置: -1.1、打开“控制面板” —— “程序” —— “启用或关闭Windows功能” —— 勾选 “适用于Linux的Windows子系统” -2、设置: -2.1、打开“设置”...

静以修身2025
昨天
2
0
init 0-6 (启动级别:init 0,1,2,3,4,5,6)

启动级别: init 0,1,2,3,4,5,6 这是个很久的知识点了,只是自己一直都迷迷糊糊的,今天在翻出来好好理解下。。 0: 停机 1:单用户形式,只root进行维护 2:多用户,不能使用net file system...

圣洁之子
昨天
2
0
Android Camera HAL浅析

1、Camera成像原理介绍 Camera工作流程图 Camera的成像原理可以简单概括如下: 景物(SCENE)通过镜头(LENS)生成的光学图像投射到图像传感器(Sensor)表面上,然后转为电信号,经过A/D(模数转...

天王盖地虎626
昨天
2
0
聊聊Elasticsearch的ProcessProbe

序 本文主要研究一下Elasticsearch的ProcessProbe ProcessProbe elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/monitor/process/ProcessProbe.java public class ProcessProb......

go4it
昨天
3
0
mysql PL(procedure language)流程控制语句

在MySQL中,常见的过程式SQL语句可以用在存储体中。其中包括IF语句、CASE语句、LOOP语句、WHILE语句、ITERATE语句和LEAVE语句,它们可以进行流程控制。 IF语句相当于Java中的if()...else if(...

edison_kwok
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部