树的高度C++(dfs)

news/2024/2/24 6:51:57/文章来源:https://blog.csdn.net/qq_46380990/article/details/135581878

树是一种特殊的图结构,有根树是一个有固定根的树。
现在给定一棵有根树,编程求出树中所有节点到指定的根节点最远距离。

输入格式
第一行是两个整数 N,M,表示数的顶点数和根节点的编号。接下来 N−1 行,每行两个整数 u,v,表示编号为 u 的节点和编号为 v的节点间有一无向条边。

输出格式
输出距离根节点最远的点到根的距离。

数据范围
1≤N≤10000,
1≤M≤N,
1≤u,v≤N

输入样例:
5 5
1 2
1 4
1 5
2 3

输出样例:
3

#include<iostream>
#include<cstring>
using namespace std;
const int N=10010,M=2*N;
int h[N],e[M],ne[M],idx;
int dis[N];
int n,m;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dis[j]=dis[u]+1;dfs(j,u);}
}
int main()
{cin>>n>>m;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(m,-1);int res=0;for(int i=0;i<n;i++)res=max(res,dis[i]);cout<<res;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925697.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vtk9.3 + Visual Studio2019 + Cmake3.28 win11 上的环境安装(这个过程网上比较多,自己记录下过程加深下印象)

开始 介绍 欢迎来到 VTK&#xff01;我们建议您首先阅读《VTK book》&#xff0c;这是一本全面的 VTK 指南&#xff0c;涵盖了其功能的所有方面。此外&#xff0c;您可能会发现探索 VTK 示例很有帮助&#xff0c;这是一组有用的参考资料&#xff0c;演示了如何使用 VTK 的不同模…

ASP.NET Core 的 Web Api 实现限流 中间件

Microsoft.AspNetCore.RateLimiting 中间件提供速率限制&#xff08;限流&#xff09;中间件。 它是.NET 7 以上版本才支持的中间件&#xff0c;刚看了一下&#xff0c;确实挺好用&#xff0c;下面给大家简单介绍一下&#xff1a; RateLimiterOptionsExtensions 类提供下列用…

Elasticsearch 7.8.0从入门到精通

安装Elasticsearch 7.8.0 官网&#xff1a;Elasticsearch 7.8.0 | Elastic 大家下载所需要的安装包即可。然后解压缩&#xff1a; Elasticsearch是通过java编写的&#xff0c;所以自带jdk。多好&#xff0c;下载Elasticsearch赠送jdk 0.0&#xff0c;不过一般我们用自己的jdk…

利用Lambda表达式实现vector中pair/结构体的排序

众所周知&#xff0c;对于vector<pair<int, int> >若直接使用sort排序&#xff0c;会默认按照pair的第一个关键字从小到大进行排序&#xff1a; #include <bits/stdc.h>using namespace std;int main() {vector<pair<int, int> > p;p.push_back…

select子句简单查询

Oracle从入门到总裁:https://blog.csdn.net/weixin_67859959/article/details/135209645 目录 数据查询 起别名 连接 ​编辑 去重 ​编辑 另外补充几个不常用的命令 如果要进行查询,那么需要使用数据操纵语言&#xff08;Data Manipulation Language&#xff0c;DML&am…

EChars

1.引入 Apache ECharts <!DOCTYPE html> <html><head><meta charset"utf-8" /><!-- 引入刚刚下载的 ECharts 文件 --><script src"echarts.js"></script></head> </html> 2. <!-- 为 ECharts 准…

[自动驾驶算法][从0开始轨迹预测]:二、自动驾驶系统中常用的坐标系及相应的转换关系

自动驾驶中常见的坐标系与坐标转换 1. 传感器坐标系1.1 相机坐标系统1) 相机相关基础知识2) 相机各坐标系图像/像素坐标系相机坐标系像平面坐标系 3) 相机各坐标系之间的转换像平面坐标系到像素坐标系的转换&#xff08;平移缩放变换&#xff09;相机坐标系转像平面坐标系&…

tcpdump常用参数以及wireshark密文解密

tcpdump常用参数以及wireshark密文解密 文章目录 一、tcpdump命令和常用参数二、在wireshark中协议解析 tcpdump常用参数 一、tcpdump命令和常用参数 tcpdump常用命令&#xff1a;tcpdump -i eth0 src host 11.6.224.1 and udp port 161 -s 0 -w 161.pcap &#xff08;161为sn…

自学Python,需要注意哪些?

为什么要学习Python&#xff1f; 在学习Python之前&#xff0c;你不要担心自己没基础或“脑子笨”&#xff0c;我始终认为&#xff0c;只要你想学并为之努力&#xff0c;就能学好&#xff0c;就能用Python去做很多事情。在这个喧嚣的时代&#xff0c;很多技术或概念会不断兴起…

解决BigDecimal序列化科学计数法前端展示问题(大坑)

解决BigDecimal序列化科学计数法前端展示问题(大坑) 前言&#xff1a;在生产中出现一个问题&#xff0c;就是BigDecimal类型的字段在前端页面展示变成科学计数法&#xff0c;通过排查&#xff0c;发现里面的坑还是挺多的&#xff0c;所以特意记录下处理过程。Json序列化&#x…

ubuntu设置每天定时关机

ubuntu设置每天定时关机 终端输入命令&#xff1a; sudo crontab -e输入密码&#xff0c;回车。 我这里使用nano作为编辑器&#xff0c;你可以选择vim。 在末尾输入以下命令&#xff1a; 59 23 * * * sudo -u root shutdown now设置&#xff1a;每天23:59分&#xff0c;电脑…

深度强化学习的变道策略:Harmonious Lane Changing via Deep Reinforcement Learning

偏理论&#xff0c;假设情况不易发生 摘要 多智能体强化学习的换道策略&#xff0c;不同的智能体在每一轮学习后交换策略&#xff0c;达到零和博弈。 和谐驾驶仅依赖于单个车辆有限的感知结果来平衡整体和个体效率&#xff0c;奖励机制结合个人效率和整体效率的和谐。 Ⅰ. 简…

Visual Studio 2022 成功配置QT5.12.10

目录 下载并安装Visual Studio 2022 Qt5.12.10下载 Qt5.12.10安装 Qt VS Tools for Visual Studio 2022下载 Visual Studio 2022配置 测试 下载并安装Visual Studio 2022 下载社区版并安装&#xff0c;这个比较快。 Qt5.12.10下载 官网下载很慢&#xff0c;还不如百度网…

论文笔记(四十)Goal-Auxiliary Actor-Critic for 6D Robotic Grasping with Point Clouds

Goal-Auxiliary Actor-Critic for 6D Robotic Grasping with Point Clouds 文章概括摘要1. 介绍2. 相关工作3. 学习 6D 抓握政策3.1 背景3.2 从点云抓取 6D 策略3.3 联合运动和抓握规划器的演示3.4 行为克隆和 DAGGER3.5 目标--辅助 DDPG3.6 对未知物体进行微调的后视目标 4. 实…

数据分析-Pandas如何整合多张数据表

数据分析-Pandas如何整合多张数据表 数据表&#xff0c;时间序列数据在数据分析建模中很常见&#xff0c;例如天气预报&#xff0c;空气状态监测&#xff0c;股票交易等金融场景。数据分析过程中重新调整&#xff0c;重塑数据表是很重要的技巧&#xff0c;此处选择Titanic数据…

Linux命令之服务器的网络配置hostname,sysctl,ifconfig,service,ifdown,ifup,route,ping的使用

1、查看当前主机名称&#xff0c;编辑配置文件修改主机名为你姓名拼音的首字母&#xff08;如张三&#xff0c;则为zs&#xff09; 2、查看本机网卡IP地址&#xff0c;编辑/etc/sysconfig/network-scripts/ifcfg-ens33&#xff0c;要求在一块物理网卡上绑定2个IP地址&#xff0…

【PHP】PHP利用ffmreg获取音频、视频的详细信息

目录 一、目的 二、下载并安装ffmreg 三、PHP代码 四、运行结果 一、目的 使用PHP利用ffmreg获取音频、视频的详细信息&#xff0c;音视频总时长、码率、视频分辨率、音频编码、音频采样频率、实际播放时间、文件大小。 二、下载并安装ffmreg 1、下载地址&#xff1a;htt…

探索web技术与低代码开发的融合应用

随着物联网、云计算和人工智能等技术的迅猛发展&#xff0c;现代软件开发正面临着日益增长的需求和复杂性。为了应对这一挑战&#xff0c;一种被称为低代码开发的快速、可视化开发方法逐渐崭露头角。本文将探讨低代码开发与web技术的融合应用&#xff0c;以及这种趋势对软件开发…

SDRAM小项目——命令解析模块

简单介绍&#xff1a; 在FPGA中实现命令解析模块&#xff0c;命令解析模块的用来把pc端传入FPGA中的数据分解为所需要的数据和触发命令&#xff0c;虽然代码不多&#xff0c;但是却十分重要。 SDRAM的整体结构如下&#xff0c;可以看出&#xff0c;命令解析模块cmd_decode负责…

银行储蓄系统的顶层数据流图及细化数据流图

绘制出银行储蓄系统的顶层数据流图及细化数据流图&#xff1b; 银行储蓄系统存、取款流程如下&#xff1a; 1&#xff09;业务员事先录入利率信息&#xff1b; 2&#xff09;如果是存款&#xff0c;储户填写存款单&#xff0c;业务员将存款单键入系统&#xff0c;系统更新储户存…