Cod sursa(job #1397140)

Utilizator vasica38Vasile Catana vasica38 Data 23 martie 2015 12:02:08
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#include<algorithm>

typedef struct lista
{
    int info;
    lista * next;
} * nod;


nod a[100012];
bool viz[100120];
int i,j,k,m,n,u,t,mx,poz;
int d[100120],c[100120];

void add(int x,nod &p)
{
    nod r=new lista;
    r->info=x;
    r->next=p;
    p=r;
}

void bfs(int x)
{
    int ic=1;
    int sf=1;
    c[1]=x;
    for (i=1; i<=n; ++i) viz[i]=0;
    for (i=1; i<=n; ++i) d[i]=0;
    d[x]=1;
    viz[x]=1;
    while (ic<=sf)
    {
        nod r=a[c[ic]];
        while (r)
        {
            if (!viz[r->info])
            {
                c[++sf]=r->info;
                d[r->info]=d[c[ic]]+1;
                viz[r->info]=1;
            }
        r=r->next;
        }
    ++ic;
    }
    mx=d[1];
    poz=1;
    for (i=1; i<=n; ++i)
        if (d[i]>mx)
                {
                mx=d[i];
                poz=i;
                }
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<n; ++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,a[y]);
        add(y,a[x]);
    }
    bfs(1);
    bfs(poz);
    printf("%d",mx);

return 0;
}