当前位置: 首页 > news >正文

数据结构与算法学习笔记----树与图的深度优先遍历

数据结构与算法学习笔记----树与图的深度优先遍历

@@ author: 明月清了个风
@@ first publish time: 2024.12.9
pa⭐️这里只有一道题哈哈。

Acwing 846.树的重心

给定一棵树,树中包含 n n n个节点(编号 1 ∼ n 1 \sim n 1n)和 n − 1 n - 1 n1条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

输入格式

第一行包含整数 n n n,表示树的节点数。
接下来 n − 1 n - 1 n1行,每行包含两个整数 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 1n105

输入样例

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号点):

    我们从1号点开始dfs(在这题里面其实从存在点开始就行,哪个点不重要,以后会碰到有些题对起始点也有考虑的)。

    根据题意我们将1号点删除后,会将树分为 3 3 3个连通块,如图所示,那么对于1号点来说,剩余连通块中点数的最大值就是4(图中紫色背景的连通块);

    2号点删除后,会将树分为 2 2 2个连通块,那么对于2号点来说,剩余连通块中点数的最大值就是6(图中紫色背景的连通块);

    以此类推…(需要注意的是这并不是dfs的顺序,只是用来说明题意)

在这里插入图片描述

  1. 代码思路

    既然已经考虑使用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.树的重心 给定一棵树&#xff0c;树中包含 n n n个节点&#xff08;编号 1 ∼ n 1 \sim n 1∼n&#xff09;和 n − 1 n - 1 n…...

IEEE T-RO 软体机器人手指状态估计实现两栖触觉传感

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

【NLP 14、激活函数 ② tanh激活函数】

学会钝感力&#xff0c;走向美好的方向 —— 24.12.11 一、tanh激活函数 1. tanh函数的定义 tanh是双曲正切函数&#xff08;Hyperbolic Tangent&#xff09;&#xff0c;数学表达式为 其函数图像是一个S型曲线&#xff0c;以原点 (0&#xff0c;0) 为中心对称&#xff0c;定…...

前端如何实现签名功能

1.JS实现 前端实现签名功能&#xff0c;通常是通过在页面上创建一个可绘制的区域&#xff0c;用户可以用鼠标或触摸设备进行签名。这个区域通常是一个<canvas>元素&#xff0c;结合JavaScript来处理绘制和保存签名。下面是一个简单的实现步骤&#xff1a; 1.1. 创建HTM…...

若依将数据库更改为SQLite

文章目录 1. 添加依赖项2. 更新配置文件 application-druid.yml2.1. 配置数据源2.2. 配置连接验证 3. 更新 MybatisPlusConfig4. 解决 mapper 中使用 sysdate() 的问题4.1. 修改 BaseEntity4.2. 修改 Mapper 5. 更新 YML 配置 正文开始&#xff1a; 前提条件&#xff1a;在您的…...

CRMEB Pro版v3.2源码全开源+PC端+Uniapp前端+搭建教程

一.介绍 crmeb pro版 v3.2正式发布&#xff0c;全新UI重磅上线&#xff0c;焕然一新&#xff0c;不负期待&#xff01;页面DIY设计功能全面升级&#xff0c;组件更丰富&#xff0c;样式设计更全面&#xff1b;移动端商家管理&#xff0c;让商城管理更便捷&#xff0c;还从页面…...

Docker 安装 Jenkins:2.346.3

准备&#xff1a;已安装Docker&#xff0c;已配置服务器安全组规则 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】模板匹配

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

黑马商城微服务复习(5)

MQ 一、同步调用和异步调用1. 同步调用2. 异步调用 二、RabbitMQ1. 基础使用2. 实际操作 怎么用?3. RabbitMQ虚拟主机 数据隔离4. 在JAVA中实现RabbitMQ5. 交换机种类 一、同步调用和异步调用 1. 同步调用 微服务一旦拆分&#xff0c;必然涉及到服务之间的相互调用&#xff…...

云原生基础设施指南:精通 Kubernetes 核心与高级用法

1. 云原生的诞生 随着互联网规模的不断增长&#xff0c;以及企业对敏捷开发、快速交付和高可用性的需求日益增强&#xff0c;传统的单体架构逐渐暴露出局限性&#xff0c;难以满足现代业务对动态扩展和高效迭代的要求。为此&#xff0c;云原生应运而生。 云原生是为云计算时代…...

人工智能概要

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

qt QCommandLineParser详解

1、概述 QCommandLineParser是Qt框架中提供的一个类&#xff0c;专门用于解析命令行参数。它简化了命令行参数的处理过程&#xff0c;使得开发者能够轻松定义、解析和验证命令行选项和参数。QCommandLineParser适用于需要从命令行获取输入的控制台应用程序&#xff0c;以及需要…...

力扣 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&#xff0c;相关链接2&#xff0c;已有模型调用测试&#xff08;1&#xff09;下载相关模型&#xff08;2&#xff09;Cnstd文本检测模型&#xff08;3&#xff09;模型调用解析脚本 3&#xff0c;自定义数据集训练测试&#xff08;1&#xff09;标签转换…...

解决 Flutter 在 Mac 上的编译错误

解决 Flutter 在 Mac 上的编译错误 在使用 Flutter 进行项目开发并尝试在 Mac 设备上进行编译时&#xff0c;遇到了一系列的错误信息&#xff0c;这些错误信息给项目的构建与部署带来了阻碍。 一、错误详情 在编译过程中&#xff0c;Xcode 输出了大量的信息&#xff0c;其中…...

MR30分布式IO在新能源领域加氢站的应用

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

wxPython中wx.ListCtrl用法(二)

wx.ListCtrl是一个列表组件&#xff0c;可以以列表视图&#xff08;list view&#xff09;、报表视图&#xff08;report view&#xff09;、图标视图&#xff08;icon view&#xff09;和小图标视图&#xff08;small icon view&#xff09;等多种模式显示列表。 一、方法 __…...

kubernetes 资源汇总

kubernetes 资源汇总 官网 英文文档 官方英文文档 中文文档 官方中文文档 github github源码地址 培训认证 也就是linux基金会的认证&#xff0c;上面也提供培训课程 下载资源 官网下载资源&#xff0c;国内的话k8s镜像下载不了&#xff0c;要去镜像站 在线练习 killer…...

每日一题(对标gesp三级答案将在第二天公布)

编程题 题目描述&#xff1a; 小杨为数字4,5,6和7设计了一款表示形式&#xff0c;每个数字占用了66的网格。数字4,5,6和7的表示形式如下&#xff08;此处自行设计复杂一些的表示形式示例&#xff09;&#xff1a; 数字4&#xff1a; …. …. …. …. *… 数字5&#xff1a; …...

让 Win10 上网本 Debug 模式 QUDPSocket 信号槽 收发不丢包的方法总结

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

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...