[AcWing]846. 树的重心(C++实现)树与图的dfs模板题

news/2024/4/15 22:14:21

[AcWing]846. 树的重心(C++实现)树与图的dfs模板题

  • 1. 题目
  • 2. 读题(需要重点注意的东西)
  • 3. 解法
  • 4. 可能有帮助的前置习题
  • 5. 所用到的数据结构与算法思想
  • 6. 总结

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路:用深度优先搜索的思想,在每个节点处可以通过递归得到子节点总的数量,然后就可以求出除去每个节点后的最大连通子图的节点数量,最后输出最小的那个最大连通子图的节点数量即可。

如果对递归思想有疑问的同学,建议先划到下方,4. 可能有帮助的前置习题,在给出的链接中复习一下递归的思想。弄清楚递归是如何求得每个节点的子树的总的节点数量的。

我们将该问题分解为如下四个子问题:

1、树的重心的含义?
2、图是怎么存储的?
3、图是怎么遍历的?
4、怎么求除去该数后最大连通子图的节点数量?


1、树的重心的含义
有这样一幅无向图
在这里插入图片描述

去除1后,剩下的连通块数的最大值为6,有6个节点
在这里插入图片描述

同理,可以求出去除每个节点后,剩下的连通块数的最大值为,如下图红色标记
在这里插入图片描述
因此,剩下的连通块数的最大值最小为5,树的重心是2或者3


2、图是怎么存储的?
要想使用dfs来遍历树或图,首先要知道图是怎么存储的
为了简便,我们在这里使用有向图来说明图的存储方式。
图一般用邻接表来存储,邻接表是由数组实现的
如有这样一个有向图
在这里插入图片描述

其相应的邻接表为
在这里插入图片描述
那么在加入一条边,在代码中如何实现呢?
其实其实质就是链表的插入,如在2节点后插入一条到8的边
在这里插入图片描述
在这里插入图片描述
其用代码实现就是

e[idx] = 8,ne[idx] = h[2],h[2] = idx ,idx ++ ;

抽象出来,在插入一条从a到b的边的代码就是

e[idx] = b,ne[idx] = h[a],h[a] = idx ,idx ++ ;

3、图是怎么遍历的?
现在我们知道如何插入一条边了,那么如何遍历这个邻接表呢?
对于上述的数组h,我们来尝试通过输入的节点u来遍历它
在这里插入图片描述
对于输入的节点u,起始节点是 h[u],下一个节点是ne[u],终止条件是 ne[u] = -1;
因此遍历的代码是

for(int i = h[u];i != -1; i = ne[i])

4、怎么求除去该数后最大连通子图的节点数量?

  • 用sum保存输入的u节点的子树的节点数
int s = dfs(j); // s为j的子树的节点数
size = max(size, s); // ???
sum += s;
  • 用size保存最大连通块的节点数量
    子树的节点数总节点减去子树的节点相比哪个大。
    (因为除去某个节点时,子树为一个连通块,总节点减去子树为另一个连通块,size要保存这两个连通块中较大的一个)
 size = max(size, s); // 子树也是一个连通块,也需要考虑在size中......size = max(size, n - sum - 1);
  • 用ans保存剩余各个节点的连通块数的最大值的最小值,只需要在每个节点求出最大连通块的数量时比较一下,取较小的那一个即可
ans = min(ans, size);

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010, M = N * 2;int n;
// h[N] 表示有N个槽
// e[M], ne[M], idx含义与单链表一致
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N]; // 表示哪些点已经遍历过了// 插入一条a到b的边
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 深度优先搜索dfs
int dfs(int u)
{st[u] = true; // 当前节点已经被搜索过了int size = 0, sum = 0;for (int i = h[u]; i != -1; i = ne[i]) // 遍历数的所有边{int j = e[i];if (!st[j]){int s = dfs(j);size = max(size, s);sum += s;}}size = max(size, n - sum - 1);ans = min(ans, size);return sum + 1;
}int main()
{scanf("%d", &n);memset(h, -1, sizeof h);for (int i = 0; i < n - 1; i ++ ){int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}dfs(1);printf("%d\n", ans);return 0;
}

4. 可能有帮助的前置习题

  • [AcWing]842. 排列数字(C++实现)dfs模板题,递归思想的解释 (主要是其中的递归思想!!)

5. 所用到的数据结构与算法思想

  • 递归
  • dfs

6. 总结

dfs遍历树和图的模板题,需要好好理解递归的思想,推荐熟记全部代码。


http://www.ppmy.cn/news/187909.html

相关文章

[图表]pyecharts模块-柱状图

[图表]pyecharts模块-柱状图 先来看代码&#xff1a; from pyecharts.charts import Bar from pyecharts.faker import Faker from pyecharts.globals import ThemeTypec (Bar({"theme": ThemeType.MACARONS}).add_xaxis(Faker.choose()).add_yaxis("商家A&q…

如何实现生成压缩包?

平时我们需要使用到压缩文件操作,压缩文件可以节省磁盘空间;且压缩文件更小,便于网络传输,效率高,下面我们就来了解thinkphp的压缩解压相关操作 在PHP中有一个ZipArchive类,专门用于文件的压缩解压相关操作 在ZipArchive类中主要使用到了如下方法: 1:open(打开一个压…

90后测试员:“入职阿里,这一次,我决定不跳槽了...”

所谓“舒适”生活 记得上一份工作是去年听从了朋友的意见&#xff0c;“你一定要找一份舒适的工作&#xff0c;这样你一天就有好多时间玩&#xff0c;好多时间干自己想干的事情&#xff0c;摸鱼真香&#xff01;” 在这份“教导”下&#xff0c;开始了我的找工作之旅&#xf…

缺项目经验的看过来,真实的软件测试实战项目来了

1.web自动化项目 这是一个电商项目&#xff0c;你可以在网站上购买各种宠物。 常见的电商网站操作在这个项目中都可以找到&#xff0c;比如注册&#xff0c;登录&#xff0c;查找商品&#xff0c;选择商品&#xff0c;添加购物车&#xff0c;下单&#xff0c;查看定位&#xf…

华为鸿蒙智慧屏_国产系统先行者!华为鸿蒙系统首次现身:智慧屏+升降式镜头+国产芯...

众所周知&#xff0c;华为自从开始登上了美方的“实体名单”之后&#xff0c;便开始频频受到限制&#xff0c;在这一段时间里&#xff0c;对于华为而言&#xff0c;可谓是一波三折&#xff0c;所以同样也牵动着无数国人的心&#xff0c;实际上&#xff0c;华为并没有因此而受到…

基于android 10的国产手机,国产手机再次发力:骁龙855 Plus+安卓10.0系统!

原标题&#xff1a;国产手机再次发力&#xff1a;骁龙855 Plus安卓10.0系统&#xff01; 在2019年上半年&#xff0c;一加这家国产智能手机厂商发布了一加7系列&#xff0c;也即包含了一加7和一加7 Pro这两款手机。值得注意的是&#xff0c;在前几年&#xff0c;坚持只做旗舰手…

大可乐android 4.3刷机包,国产Android 4.2:

国产Android 4.2&#xff1a;大可乐2代 大可乐手机如今已经出到了第二代&#xff0c;性能方面的提升是该机最为显著的特点&#xff0c;这里包括5.3英寸的大屏&#xff0c;以及高性价比的MT6589四核处理器&#xff0c;甚至连运行内容也改换成了2GB RAM&#xff0c;这使得整机运行…

国产手机 android 6,小米5/魅族PRO 6/华为P9横评:国产Android手机大比拼

OFweek显示网讯 2016 年仅仅过半&#xff0c;除了国际阵营的三星 Galaxy S7 和 LG G5 之外&#xff0c;在国内 Android 手机市场颇具分量的小米、魅族和华为也轮番上阵了自家的重磅新品&#xff0c;令上半场的比拼大有看头。在下半场更精彩的新品上演之前&#xff0c;编辑部凑齐…

华为p40鸿蒙2.0演示,华为P40强硬登场:屏下镜头+鸿蒙2.0+徕卡5摄,国产骄傲绝不服输...

2019年应该是华为的幸运之年&#xff0c;在这一年里华为发布的款款机型都取得了空前的成功&#xff0c;无论是华为Mate X还是华为P30系列以及刚发布不就的华为Mate 30系列都成为了叫好又叫座的国民旗舰机型&#xff0c;在产品方面华为无疑是成功的。但同时今年又是华为的倒霉之…

国产手机品牌利润份额快速提升,在中高端市场取得突破

国产手机品牌此前一直面临增收不增利的局面&#xff0c;而据市调机构counterpoint发布的今年二季度的数据显示&#xff0c;国产手机品牌占全球智能手机市场的利润份额正在快速提升。 国产手机品牌占全球手机市场利润份额快速上升 市调机构counterpoint发布的数据显示&#xff0…

Kinect与TOF、双目、结构光相机比较相机国产、非国产统计参数对比分析

Kinect与TOF、双目、结构光相机比较相机国产、非国产统计参数对比分析 Kinect v1和Kinect v2之间的参数比较 从图中可以看出&#xff0c;Kinect v2的表现比Kinect v1要好得多&#xff1a;首先最令人印象深刻的是分辨率的提高&#xff0c;v2达到了1080p&#xff0c;甚至视野也大…

国产小家电品牌如何用dtc模式打造新中产超爆款?

又是一年618&#xff0c;买买买的时刻也是各大企业品牌最能够验证自己的卖货能力的时刻。回顾上一个全民购物狂欢节点&#xff0c;该高端智能生活电器品牌全渠道成交额突破4.1亿元&#xff0c;&#xff08;截止2020年11月12日0点&#xff09;成交量破13万台&#xff0c;再创新纪…

面阵相机靶面详解and镜头选择andFA镜头视野计算

工业相机靶面详解 工业相机的靶面也就是相机成像芯片的尺寸&#xff0c;一般描述相机靶面采用英寸来描述&#xff0c;在相机芯片中&#xff0c;1英寸为16mm。 通常说的2/3英寸靶面的相机意思就是&#xff0c;相机芯片对角线的尺寸为2/3英寸&#xff0c;也就是16mm*(2/3)约等于…

透过4亿元融资看科视光学“国产替代”的野望

2022年的北京冬奥会&#xff0c;是一场中国科技创新成果的“武装”盛会&#xff0c;每一项技术硬件拿出来&#xff0c;都是中国人的骄傲。而这些企业背后&#xff0c;同样站着服务商的身影。 近日&#xff0c;高端光学装备及机器视觉光源厂商科视光学完成了近4亿元C轮融资&…

家用什么牌子投影仪好?国产投影仪品牌

近两年来家用投影仪火得一塌糊涂&#xff0c;很多朋友都来问我该选什么牌子的投影仪好&#xff1f;说实话&#xff0c;现在的投影仪市场更新换代很快&#xff0c;所以个人觉得光看牌子是不客观的&#xff0c;只有我们自己真正了解那些对投影仪来说难以突破的技术&#xff0c;才…

豆瓣最新国产电影Top10

我这里整理了下豆瓣目前来说排名最高的国产电影Top10 Top1 经典台词&#xff1a; 1.真虞姬&#xff0c;假霸王 2.不疯魔不成活&#xff08;巩俐当时颜值爆表啊&#xff09; 经典画面&#xff1a; Top2 经典台词&#xff1a; 1.曾经有一份真挚的爱情摆在我的面前&#xff0…

国产电视剧中电脑高手镜头是怎么拍出来的

今天看某电视剧&#xff0c;看到剧中人物在设计软件的镜头&#xff0c;突发奇想分析了下这种镜头是怎么拍出来的&#xff08;其实没有恶意&#xff0c;也不想批判什么&#xff0c;因为我从来不带着必须真实的要求看电视&#xff09;&#xff0c;具体哪部电视就不说了&#xff0…

机器视觉相机镜头的选择

一般而言&#xff0c;机器视觉产业链主要包括上游的零部件级市场、中游的系统集成/整机装备市场和下游的应用市场。 1、相机 1.1、相机的分类&#xff0c;CCD相机与CMOS相机 CCD称为电荷耦合器件&#xff0c;它集光电转换及电荷存储、电荷转移、信号读取于一体&#xff0c;是…

php获取手机品牌,9 大国产手机品牌相机水印大比拼,哪款才是你的最爱?

对于各大国产品牌手机用户来说&#xff0c;相机水印这个小玩意儿应该都不陌生。这一设计原本的用途是华为用来彰显自己的徕卡逼格&#xff0c;后来逐渐被友商们用作互联网宣传品牌的渠道&#xff0c;以及用户在社交平台彰显个性的一种标签。 甚至有部分不支持自动添加相机水印的…

gcc-g++使用编译链接理解

在讲gcc/g使用之前我们先讲一下背景&#xff0c;编译链接 编译链接我们之前讲过一次&#xff0c;但是这里在深入理解一下编译链接&#xff0c;以及我们看一下现象 编译链接 首先&#xff0c;编译链接可以分为四步&#xff1a; 1.预处理 2.编译 3.汇编 4.链接 预处理 我…
最新文章