Pagini recente » Cod sursa (job #746876) | Cod sursa (job #154071) | Cod sursa (job #872314) | Cod sursa (job #1009042) | Cod sursa (job #1293941)
#include<cstdio>
#include<vector>
using namespace std;
const int NMAX = 100000;
vector <int> v[NMAX + 2];
int h[NMAX + 2], pred[NMAX + 2], sol[NMAX + 2];
bool viz[NMAX + 2];
void dfs(int k)
{
int i;
viz[k] = true;
for(i = 0; i < v[k].size(); i++)
if(!viz[v[k][i]])
{
pred[v[k][i]] = k;
dfs(v[k][i]);
}
if(h[k] + 1 > h[pred[k]])
h[pred[k]] = h[k] + 1;
}
int main()
{
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
int n, i, x, y;
scanf("%d", &n);
for(i = 1; i < n; i++)
{
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
for(i = 1; i <= n; i++)
if(v[i].size() == 1)
h[i] = 1;
dfs(1);
int max1 = 0, ind1;
for(i = 0; i < v[1].size(); i++)
if(h[v[1][i]] > max1)
{
max1 = h[v[1][i]];
ind1 = v[1][i];
}
int max2 = 0, ind2;
for(i = 0; i < v[1].size(); i++)
if(h[v[1][i]] > max2 && (h[v[1][i]] < max1 || (h[v[1][i]] == max1 && v[1][i] != ind1)))
{
max2 = h[v[1][i]];
ind2 = v[1][i];
}
printf("%d\n", max1 + max2 + 1);
/* int poz = max1 - 1;
sol[max1 + 1] = 1;
sol[max1] = ind1;
int hc = h[ind1];
sol[0] = max1 + 1;
while(hc > 1)
{
for(i = 0; i < v[ind1].size(); i++)
if(h[v[ind1][i]] == hc - 1)
{
sol[poz] = v[ind1][i];
poz --;
ind1 = v[ind1][i];
hc --;
break;
}
}
hc = h[ind2];
sol[++sol[0]] = ind2;
while(hc > 1)
{
for(i = 0; i < v[ind2].size(); i++)
if(h[v[ind2][i]] == hc - 1)
{
sol[++sol[0]] = v[ind2][i];
ind2 = v[ind2][i];
hc --;
break;
}
}
for(i = 1; i <= sol[0]; i ++)
printf("%d ", sol[i]);
printf("\n");*/
return 0;
}