Cod sursa(job #1651226)

Utilizator andreiudilaUdila Andrei andreiudila Data 12 martie 2016 19:05:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n,i,j,q[100001],dist[100001],x,y,nodc,maxx,r,l,ind;
typedef struct celula{

int val;
celula *next;

}*lista;

lista a[100001],c;

int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>x>>y;

        c=new celula;
        c->val=x;
        c->next=a[y];
        a[y]=c;

        c=new celula;
        c->val=y;
        c->next=a[x];
        a[x]=c;

    }

    q[1]=1;
    l=1; r=1;
    while(l<=r)
    {
        nodc=q[l];
        ++l;

        for(lista i=a[nodc];i!=NULL;i=i->next)
        {
            if(dist[i->val]==0)
            {
                dist[i->val]=dist[nodc]+1;
                q[r+1]=i->val;
                ++r;
            }
        }
    }

    for(i=1;i<=n;++i)
    {
        if(dist[i]>maxx) {

        maxx=dist[i];
        ind=i;
        }
    }

    memset(dist,0,sizeof(dist));
    maxx=0;

    q[1]=ind;
    l=1; r=1;
    while(l<=r)
    {
        nodc=q[l];
        ++l;

        for(lista i=a[nodc];i!=NULL;i=i->next)
        {
            if(dist[i->val]==0)
            {
                dist[i->val]=dist[nodc]+1;
                q[r+1]=i->val;
                ++r;
            }
        }
    }

    for(i=1;i<=n;++i)
        maxx=max(maxx,dist[i]);

        fout<<maxx+1;
    return 0;
}