数据结构与算法学习笔记----树与图的深度优先遍历
数据结构与算法学习笔记----树与图的深度优先遍历
@@ author: 明月清了个风
@@ first publish time: 2024.12.9
pa⭐️这里只有一道题哈哈。
Acwing 846.树的重心
给定一棵树,树中包含 n n n个节点(编号 1 ∼ n 1 \sim n 1∼n)和 n − 1 n - 1 n−1条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
输入格式
第一行包含整数 n n n,表示树的节点数。
接下来 n − 1 n - 1 n−1行,每行包含两个整数 a a a和 b b b,表示点 a a a和 b b b之间存在一条边。
输出格式
输出一个整数 m m m,表示将重心删除后,剩余各个连通块中点数的最大值。
数据范围
1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例
4
思路
首先是建树,使用的还是邻接表的方式,这个在哈希表中讲过了,如果不太懂可以去看一下,这题中的注意点就是因为是无向边,所以存的边数需要乘两倍
为什么用dfs:根据题意,我们需要在树中找到重心,而重心会将树划分为不同的连通块,我们需要统计的是不同连通块中点的数目,因此可以考虑dfs,这里大家可能会说为什么不是bfs,其实也可以,但是相对来说,bfs更强调点与点之间层级的概念,而这里我们只需要统计即可,因此dfs可能更加合适。
-
现在以输入样例中的树的形状为例解释一下题意(这里提前告诉大家重心是
1
号点):我们从
1
号点开始dfs(在这题里面其实从存在点开始就行,哪个点不重要,以后会碰到有些题对起始点也有考虑的)。根据题意我们将
1
号点删除后,会将树分为 3 3 3个连通块,如图所示,那么对于1
号点来说,剩余连通块中点数的最大值就是4
(图中紫色背景的连通块);将
2
号点删除后,会将树分为 2 2 2个连通块,那么对于2
号点来说,剩余连通块中点数的最大值就是6
(图中紫色背景的连通块);以此类推…(需要注意的是这并不是dfs的顺序,只是用来说明题意)
-
代码思路
既然已经考虑使用dfs进行解决,那么就要考虑dfs中具体需要维护的内容了。
-
首先最基本的就是连通块中点的统计,这很简单,伪代码如下
以上面的图(a)距离来说,我们
dfs(1)
后,会在for
循环中找到三个点2, 7, 4
,这里就以2
举例,那么对于2
来说,我们会搜到他能到的点是1, 8, 5
,但是我们是从1
过来的,标记了st[1] = true
,因此不会往回走了(这里是一个重点,后面会重新提到),所以dfs(2)
中的for
循环只会遍历到8, 5
,那么对于这两个点也是同样的情况,不会往回走,但是他们的for
中没有别的点可以走了,因此就是直接返回sum + 1 = 0 + 1 = 1
。int dfs(int u) {st[u] = true; // 标记这个点搜过了int sum = 0; // 记录以这个点所在连通块的点的总数for(int i = h[u]; i != -1; i = ne[i]) // 连通块的遍历{int j = e[i]; // 取出u通向的点if(st[j]) continue; // 判断这个点搜过了没有int s = dfs(j); // 递归搜j点所在连通块的点的总数,因为这个连通块中搜过的点都会被标记,所以不会重复搜sum += s; // 加上递归搜到的总数,}return sum + 1; }
-
然后是删除该点后连通块的最大值的维护
因为我们的dfs返回的是该点所在连通块中点的总数,但是我们需要维护的是删除该点后,剩下几个连通块中点数的最大值,也就是不包含这一点,因此这个量我们需要在
for
循环中维护,因为for
循环中,我们会遍历所有当前点能去到的点并统计其所在连通块的点数int s =dfs(j)
,这就相当于将u
点删除后,他分割出的一个连通块的点的总数,因此只需要对这个量取最大值即可,增加一个量size
进行维护size = max(size, s)
,代码修改如下:int dfs(int u) {st[u] = true; // 标记这个点搜过了int size = 0; // 记录删除当前点u后分割出的连通块的点数的最大值int sum = 0; // 记录以这个点所在连通块的点的总数for(int i = h[u]; i != -1; i = ne[i]) // 连通块的遍历{int j = e[i]; // 取出u通向的点if(st[j]) continue; // 判断这个点搜过了没有int s = dfs(j); // 递归搜j点所在连通块的点的总数,因为这个连通块中搜过的点都会被标记,所以不会重复搜size = max(size, s);sum += s; // 加上递归搜到的总数,}return sum + 1; }
-
最后就是所有剩下连通块的点数的最大值的最小值
在上述dfs过程中,我们就可以维护出删除每个点后分割出的连通块的点数的最大值,要求最小值只需要用一个全局变量
ans
进行维护就行,这里的一个注意点就是在上面第一点蓝字中提到的重点。还是以点2
为例子,我们在第一层dfs(1)
中已经将st[1] = true
标记了,但是根据树的重心的定义,删除点2
后,图(b)中紫色背景部分同样也是一个连通块,但是因为1
被标记了所以在dfs(2)
的for
中不会向1
走,那么1
所在连通块的点数如何处理呢,这同样有可能改变最后size
维护的大小,我们需要在for
循环后加一步更新操作size = max(size, n - sum - 1);
,已知当前点所在连通块的数量(包含当前点)是我们的返回值sum + 1
,那么所有点减去这个量n - sum - 1
,就是往回走的剩下那个连通块的点的数量,这里再和for
循环中维护的size
取个最大值就能保证没有遗漏了。
-
代码
#include <iostream>
#include <cstring>using namespace std;const int N = 100010;int n;
int h[N], e[N * 2], ne[N * 2], idx; // 无向边,因此要存两倍的量,节点数不用两倍
bool st[N]; // flag数组,标记每个点是否被dfs过
int ans = N; // 要求的值是最小值,因此答案初始化为最大值void add(int a, int b) // 单链表的加边操作
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int dfs(int u) // dfs的返回值是dfs的这个点所在连通块的点的总数
{st[u] = true; // 标记这个点被搜过了 // size表示删除这个点的话,剩余每个连通块中包含点数最大值,因此初始化为0// sum表示当前dfs的点所在连通块的点的总数(不包含当前点),因此最后返回的是sum + 1int size = 0, sum = 0; for(int i = h[u]; i != -1; i = ne[i]) // 遍历这个点能去到的所有的点,dfs后就能找到他们所在连通块的点的最大值(存在size里了){int j = e[i];if(st[j]) continue; // 判断点有没有被搜过int s = dfs(j); // s存的就是这个点所在连通块包含的点的总数,size = max(size, s); // 找最大值sum += s; // 加在当前dfs的点的总数里,也就是点u所在连通块的总的点数中}// 这里是个细节,因为我们是随便找一个点开始遍历,比如这里我们搜的是1,但是我们并不知道重心是谁// 因此可能搜到后面的时候,往回走的点已经被搜过了,因此还要对比出去这个点的总数剩下的那个连通块的点的总数的大小,看图size = max(size, n - sum - 1); ans = min(ans, size);return sum + 1;
}int main()
{cin >> n;memset(h, -1, sizeof h);for(int i = 0; i < n - 1; i ++){int a, b;cin >> a >> b;add(a, b), add(b, a);}dfs(1);cout << ans << endl;return 0;
}
1; i ++){int a, b;cin >> a >> b;add(a, b), add(b, a);}dfs(1);cout << ans << endl;return 0;
}
相关文章:

数据结构与算法学习笔记----树与图的深度优先遍历
数据结构与算法学习笔记----树与图的深度优先遍历 author: 明月清了个风 first publish time: 2024.12.9 pa⭐️这里只有一道题哈哈。 Acwing 846.树的重心 给定一棵树,树中包含 n n n个节点(编号 1 ∼ n 1 \sim n 1∼n)和 n − 1 n - 1 n…...

IEEE T-RO 软体机器人手指状态估计实现两栖触觉传感
摘要:南方科技大学戴建生院士、林间院士、万芳老师、宋超阳老师团队近期在IEEE T-RO上发表了关于软体机器人手指在两栖环境中本体感知方法的论文。 近日,南方科技大学戴建生院士、林间院士、万芳老师、宋超阳老师团队在机器人顶刊IEEE T-RO上以《Propri…...

【NLP 14、激活函数 ② tanh激活函数】
学会钝感力,走向美好的方向 —— 24.12.11 一、tanh激活函数 1. tanh函数的定义 tanh是双曲正切函数(Hyperbolic Tangent),数学表达式为 其函数图像是一个S型曲线,以原点 (0,0) 为中心对称,定…...
前端如何实现签名功能
1.JS实现 前端实现签名功能,通常是通过在页面上创建一个可绘制的区域,用户可以用鼠标或触摸设备进行签名。这个区域通常是一个<canvas>元素,结合JavaScript来处理绘制和保存签名。下面是一个简单的实现步骤: 1.1. 创建HTM…...
若依将数据库更改为SQLite
文章目录 1. 添加依赖项2. 更新配置文件 application-druid.yml2.1. 配置数据源2.2. 配置连接验证 3. 更新 MybatisPlusConfig4. 解决 mapper 中使用 sysdate() 的问题4.1. 修改 BaseEntity4.2. 修改 Mapper 5. 更新 YML 配置 正文开始: 前提条件:在您的…...
CRMEB Pro版v3.2源码全开源+PC端+Uniapp前端+搭建教程
一.介绍 crmeb pro版 v3.2正式发布,全新UI重磅上线,焕然一新,不负期待!页面DIY设计功能全面升级,组件更丰富,样式设计更全面;移动端商家管理,让商城管理更便捷,还从页面…...

Docker 安装 Jenkins:2.346.3
准备:已安装Docker,已配置服务器安全组规则 1581 1、拉取镜像 [rootTseng ~]# docker pull jenkins/jenkins:2.346.3 2.346.3: Pulling from jenkins/jenkins 001c52e26ad5: Pull complete 6b8dd635df38: Pull complete 2ba4c74fd680: Pull complet…...

【OpenCV】模板匹配
理论 模板匹配是一种在较大图像中搜索和查找模板图像位置的方法。为此,OpenCV 带有一个函数 cv.matchTemplate() 。它只是在输入图像上滑动模板图像(如在 2D 卷积中),并比较模板图像下的模板和输入图像的补…...

黑马商城微服务复习(5)
MQ 一、同步调用和异步调用1. 同步调用2. 异步调用 二、RabbitMQ1. 基础使用2. 实际操作 怎么用?3. RabbitMQ虚拟主机 数据隔离4. 在JAVA中实现RabbitMQ5. 交换机种类 一、同步调用和异步调用 1. 同步调用 微服务一旦拆分,必然涉及到服务之间的相互调用ÿ…...

云原生基础设施指南:精通 Kubernetes 核心与高级用法
1. 云原生的诞生 随着互联网规模的不断增长,以及企业对敏捷开发、快速交付和高可用性的需求日益增强,传统的单体架构逐渐暴露出局限性,难以满足现代业务对动态扩展和高效迭代的要求。为此,云原生应运而生。 云原生是为云计算时代…...

人工智能概要
目录 前言1.什么是人工智能(Artificial Intelligence, AI)2.人工智能发展的三次浪潮2.1 人工智能发展的第一次浪潮2.2 人工智能发展的第二次浪潮2.3 人工智能发展的第三次浪潮 3.人工智能发展的必备三要素3.1 数据3.2 算法(algorithm…...

qt QCommandLineParser详解
1、概述 QCommandLineParser是Qt框架中提供的一个类,专门用于解析命令行参数。它简化了命令行参数的处理过程,使得开发者能够轻松定义、解析和验证命令行选项和参数。QCommandLineParser适用于需要从命令行获取输入的控制台应用程序,以及需要…...
力扣 K个一组翻转链表
K个一组翻转链表 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(ne…...

cnocr配置及训练测试
cnocr配置及训练测试 1,相关链接2,已有模型调用测试(1)下载相关模型(2)Cnstd文本检测模型(3)模型调用解析脚本 3,自定义数据集训练测试(1)标签转换…...
解决 Flutter 在 Mac 上的编译错误
解决 Flutter 在 Mac 上的编译错误 在使用 Flutter 进行项目开发并尝试在 Mac 设备上进行编译时,遇到了一系列的错误信息,这些错误信息给项目的构建与部署带来了阻碍。 一、错误详情 在编译过程中,Xcode 输出了大量的信息,其中…...

MR30分布式IO在新能源领域加氢站的应用
导读 氢能被誉为21世纪最具发展潜力的清洁能源,氢能科技创新和产业发展持续得到各国青睐。氢能低碳环保,燃烧的产物只有水,是用能终端实现绿色低碳转型的重要载体。氢能产业链分别为上游制氢、中游储运以及下游用氢。上游制氢工艺目前大部分…...

wxPython中wx.ListCtrl用法(二)
wx.ListCtrl是一个列表组件,可以以列表视图(list view)、报表视图(report view)、图标视图(icon view)和小图标视图(small icon view)等多种模式显示列表。 一、方法 __…...
kubernetes 资源汇总
kubernetes 资源汇总 官网 英文文档 官方英文文档 中文文档 官方中文文档 github github源码地址 培训认证 也就是linux基金会的认证,上面也提供培训课程 下载资源 官网下载资源,国内的话k8s镜像下载不了,要去镜像站 在线练习 killer…...
每日一题(对标gesp三级答案将在第二天公布)
编程题 题目描述: 小杨为数字4,5,6和7设计了一款表示形式,每个数字占用了66的网格。数字4,5,6和7的表示形式如下(此处自行设计复杂一些的表示形式示例): 数字4: …. …. …. …. *… 数字5: …...

让 Win10 上网本 Debug 模式 QUDPSocket 信号槽 收发不丢包的方法总结
在前两篇文章里,我们探讨了不少UDP丢包的解决方案。经过几年的摸索测试,其实方法非常简单, 无需修改代码。 1. Windows 下设置UDP缓存 这个方法可以一劳永逸解决UDP的收发丢包问题,只要添加注册表项目并重启即可。即使用Qt的信号与槽&#…...

SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...