Cod sursa(job #1814512)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 24 noiembrie 2016 09:09:45
Problema Diametrul unui arbore Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>
int nr,lista[100001],nod[200001],next[200001],mark[100001],coada[100001],mark1[100001];
void add(int x,int y)
{
    nr++;
    nod[nr]=y;
    next[nr]=lista[x];
    lista[x]=nr;
}
int main()
{
    int n,i,x,y,p,u,max,z;
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    coada[1]=n/2;
    p=u=1;
    mark[n/2]=1;
    while(p<=u)
    {
        x=lista[coada[p]];
        while(x)
        {
            if(mark[nod[x]]==0)
                mark[nod[x]]=mark[coada[p]]+1,coada[++u]=nod[x];
            x=next[x];
        }
        p++;
    }
    max=0;
    z=0;
    for(i=1; i<=n; i++)
        if(mark[i]>max)
        {
            max=mark[i];
            z=i;
        }
    coada[1]=z;
    p=u=1;
    mark1[z]=1;
    max=0;
    while(p<=u)
    {
        x=lista[coada[p]];
        while(x)
        {
            if(mark1[nod[x]]==0){
                mark1[nod[x]]=mark1[coada[p]]+1,coada[++u]=nod[x];
                if(mark1[nod[x]]>max)
                    max=mark1[nod[x]];
            }
            x=next[x];
        }
        p++;
    }
    printf("%d\n",max);

    return 0;
}