Pagini recente » Cod sursa (job #147822) | Cod sursa (job #600324) | Cod sursa (job #1051896) | Cod sursa (job #2520016) | Cod sursa (job #2762367)
#include <bits/stdc++.h>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int n,d1[100005],d2[100005],rad,t[100005],pst;
vector<int>a[100005];
queue<int>q;
void citire()
{
in >> n;
for (int i = 1; i < n; i++)
{
int x,y;
in >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
t[y] = x;
}
for (int i = 1; i <= n; i++)
if (t[i] == 0)
rad = i;
}
void BFS1()
{
q.push(rad);
d1[rad] = 1;
while (!q.empty())
{
int nod = q.front();
q.pop();
for (int i = 0; i < a[nod].size(); i++)
{
if (d1[a[nod][i]] == 0)
{
q.push(a[nod][i]);
d1[a[nod][i]] = 1 + d1[nod];
}
}
}
int maxim = 0;
for (int i = 1; i <= n; i++)
if (d1[i] > maxim)
{
maxim = d1[i];
pst = i;
}
}
void BFS2()
{
q.push(pst);
d2[pst] = 1;
while (!q.empty())
{
int nod = q.front();
q.pop();
for (int i = 0; i < a[nod].size(); i++)
{
if (d2[a[nod][i]] == 0)
{
q.push(a[nod][i]);
d2[a[nod][i]] = 1 + d2[nod];
}
}
}
int maxim = 0;
for (int i = 1; i <= n; i++)
maxim = max(maxim,d2[i]);
out << maxim;
}
int main()
{
citire();
BFS1();
BFS2();
return 0;
}