树的高度C++(dfs)

发布时间:2024年01月14日

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

输入格式
第一行是两个整数 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;
}
文章来源:https://blog.csdn.net/qq_46380990/article/details/135581878
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。