树的高度C++(dfs)

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

输入格式
第一行是两个整数 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;
}

相关推荐

  1. 高度C++(dfs)

    2024-01-16 22:48:04       37 阅读
  2. CDF和PDF比较

    2024-01-16 22:48:04       28 阅读
  3. 线段CF 练习题

    2024-01-16 22:48:04       22 阅读
  4. CCF PTA 2023年5月C++天空之城

    2024-01-16 22:48:04       12 阅读

最近更新

  1. 微软edge浏览器全解析

    2024-01-16 22:48:04       0 阅读
  2. react根据后端返回数据动态添加路由

    2024-01-16 22:48:04       0 阅读
  3. RedHat运维-Ansible自动化运维基础22-rhel-system-roles

    2024-01-16 22:48:04       0 阅读
  4. 深入浅出:Scikit-Learn基础教程

    2024-01-16 22:48:04       0 阅读
  5. python class

    2024-01-16 22:48:04       0 阅读
  6. 10.pwn ROP(栈溢出攻击的核心)

    2024-01-16 22:48:04       0 阅读
  7. sklearn基础教程

    2024-01-16 22:48:04       0 阅读
  8. 跨境支付新篇章:引领电商潮流

    2024-01-16 22:48:04       0 阅读

热门阅读

  1. Electron:Electron整合vue

    2024-01-16 22:48:04       29 阅读
  2. 单元测试@Parameters

    2024-01-16 22:48:04       36 阅读
  3. Spring MVC(三) 国际化

    2024-01-16 22:48:04       26 阅读
  4. 力扣-三数之和

    2024-01-16 22:48:04       39 阅读
  5. ACM板子

    ACM板子

    2024-01-16 22:48:04      36 阅读
  6. rust嵌入式开发补充

    2024-01-16 22:48:04       38 阅读
  7. mac安装mysql和docker

    2024-01-16 22:48:04       34 阅读