树是一种特殊的图结构,有根树是一个有固定根的树。
现在给定一棵有根树,编程求出树中所有节点到指定的根节点最远距离。
输入格式
第一行是两个整数 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;
}