Cod sursa(job #1265805)

Utilizator raztaapDumitru raztaap Data 17 noiembrie 2014 19:44:18
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
struct nod{int nd; nod *next;};
nod *L[100100];
struct coada{int val; int d;};
coada C[100100], X;
int ic, sf, n, uz[100100];
void citire()
{
    nod *p;
    int x, y, i;
    scanf("%d", &n);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d", &x, &y);
        p=new nod;
        p->nd=y;
        p->next=L[x];
        L[x]=p;
        p=new nod;
        p->nd=x;
        p->next=L[y];
        L[y]=p;
    }
}
void bfs(int poz)
{
    nod *p;
    ic=sf=1;
    C[ic].val=poz;
    C[ic].d=1;
    uz[poz]=1;
    while(ic<=sf)
    {
        X=C[ic++];
        p=L[X.val];
        while(p)
        {
            if(!uz[p->nd])
            {
                C[++sf].val=p->nd;
                uz[p->nd]=1;
                C[sf].d=X.d+1;
            }
            p=p->next;
        }
    }
}
void sterge()
{
    int i;
    for(i=1;i<=n;++i)
        uz[i]=0;
}
void rezolva_problema()
{
    citire();
    bfs(1);
    sterge();
    bfs(C[sf].val);
    printf("%d\n", C[sf].d);
}
int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    rezolva_problema();
    return 0;
}