Mai intai trebuie sa te autentifici.
Cod sursa(job #1681884)
Utilizator | Data | 9 aprilie 2016 19:43:26 | |
---|---|---|---|
Problema | Diametrul unui arbore | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.2 kb |
#include <cstdio>
#include <vector>
using namespace std;
const int nmax=100000;
int v[nmax],n,x,y,i,j,q,k,p,cost;
bool viz[nmax];
vector <int> a[nmax];
void citire()
{
freopen("darb.in","r",stdin);
freopen("darb.out","w",stdout);
scanf("%d",&n);
for(x=1;x<=n;x++)
{
scanf("%d %d",&i,&j);
a[i].push_back(j);
a[j].push_back(i);
}
}
int main()
{
citire();
v[1]=1; viz[1]=1;
q=0; k=1; p=0;
do
{
for(x=q+1;x<=q+k;x++)
{
for(y=0;y<a[v[x]].size();y++)
if (!viz[a[v[x]][y]])
viz[a[v[x]][y]]=1,
++p,
v[q+k+p]=a[v[x]][y];
}
q+=k; k=p; p=0;
}while(k>0);
for(x=1;x<=n;x++) viz[x]=0;
v[1]=v[q]; viz[v[q]]=1;
q=0; k=1; p=0;
do
{
cost++;
for(x=q+1;x<=q+k;x++)
{
for(y=0;y<a[v[x]].size();y++)
if (!viz[a[v[x]][y]])
viz[a[v[x]][y]]=1,
++p,
v[q+k+p]=a[v[x]][y];
}
q+=k; k=p; p=0;
}while(k>0);
printf("%d\n",cost);
return 0;
}