You are given an
unweighted, undirected tree. Write a program to output the length of the
longest path (from one node to another) in that tree. The length of a path in
this case is number of edges we traverse from source to destination.
Input. The first line of the input file contains one integer n – number of nodes in the tree (0 < n ≤ 10000). Next n – 1 lines contain n – 1 edges of that tree. Each line contains a pair (u, v)
means there is an edge between node u
and node v (1 ≤ u, v
≤ n).
Output. Print the length of the longest path on one line.
Sample Input
3
1 2
2 3
Sample Output
2
дерево
Запустим поиск в ширину из любой (например, первой) вершины. Найдем вершину v, лежащую от нее на наибольшем расстоянии. Запустим поиск в ширину из вершины v. Пусть от нее на максимальном расстоянии лежит вершина u. Тогда расстояние между v и u будет искомым наибольшим путем на дереве.
Реализация
алгоритма
#include <cstdio>
#include <deque>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX
10001
#define INF
2100000000
using namespace std;
int i, j,
n;
int b, e,
dist, tests;
vector<vector<int> > m;
deque<int> q;
int
d[MAX];
int bfs(int v)
{
q.clear();
q.push_back(v);
while(!q.empty())
{
int v =
q.front(); q.pop_front();
for(int i = 0; i < m[v].size(); i++)
{
int to =
m[v][i];
if (d[to]
== -1)
{
d[to] = d[v] + 1;
q.push_back(to);
}
}
}
return
max_element(d+1,d+n+1) - d;
}
int main(void)
{
scanf("%d",&n);
m.assign(n+1,vector<int>());
for(i = 0; i
< n - 1; i++)
{
scanf("%d
%d",&b,&e);
m[b].push_back(e);
m[e].push_back(b);
}
memset(d,-1,sizeof(d));
d[1] = 0;
int v =
bfs(1);
memset(d,-1,sizeof(d));
d[v] = 0;
v = bfs(v);
printf("%d\n",d[v]);
return 0;
}