Cod sursa(job #1642665)

Utilizator stefan.friptuPetru Stefan Friptu stefan.friptu Data 9 martie 2016 15:27:13
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

vector <long> G[100001];
long maxim,d[100001],ind,n,x,y,i;

void dfs (long u,long last)
{
    d[u]=d[last]+1;
    for(long i=0;i<G[u].size();i++)
        if(!d[G[u][i]])
            dfs(G[u][i],u);
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);

    scanf("%ld",&n);

    for(i=1;i<n;i++)
    {
        scanf("%ld%ld",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs(1,0);

    for(i=1;i<=n;i++)
        if(d[i]>maxim) {maxim=d[i]; ind=i;}
    memset(d,0,sizeof(d));
    dfs(ind,0);
    maxim=0;
    for(i=1;i<=n;i++)
        if(d[i]>maxim) maxim=d[i];

    printf("%ld\n",maxim);

    return 0;
}