Cod sursa(job #1420365)

Utilizator andreii1Ilie Andrei andreii1 Data 18 aprilie 2015 12:57:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>
using namespace std;

vector<int> v[100010];
int c[100010],ok[100010],a[100010],x,y,n,lev[100010],ok1[100010],lev1[100010];
int p,u;

int main()
{
    int i,i1,maxx=0;;
    FILE *f=fopen("darb.in","r");
    FILE *g=fopen("darb.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n-1;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
        a[x]++;
        a[y]++;
    }
    p=1;u=1;c[1]=1;ok[1]=1;lev[1]=0;
    while(p<=u)
    {
        x=c[p];
        for(i=0;i<a[x];i++)
            if(ok[v[x][i]]==0)
        {
            c[++u]=v[x][i];
            ok[v[x][i]]=1;
            lev[v[x][i]]=lev[x]+1;
            if(lev[v[x][i]]>maxx){i1=v[x][i];maxx=lev[v[x][i]];}
        }
        p++;
    }
    p=1;u=1;c[1]=i1;ok1[i1]=1;lev1[i1]=0;
    while(p<=u)
    {
        x=c[p];
        for(i=0;i<a[x];i++)
            if(ok1[v[x][i]]==0)
        {
            c[++u]=v[x][i];
            ok1[v[x][i]]=1;
            lev1[v[x][i]]=lev1[x]+1;
            if(lev1[v[x][i]]>maxx)maxx=lev1[v[x][i]];
        }
        p++;
    }
    fprintf(g,"%d",maxx+1);
    fclose(f);
    fclose(g);
    return 0;
}