Cod sursa(job #1546078)

Utilizator rares1012Rares Cautis rares1012 Data 7 decembrie 2015 17:42:47
Problema Diametrul unui arbore Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#include <stdlib.h>

int tati[100001];
char comun[100001];
int distc[100001];

int main()
{
    int dist,n,i,max,j,k,q;
    FILE*fi,*fo;
    fi=fopen("darb.in","r");
    fo=fopen("darb.out","w");
    fscanf(fi,"%d",&n);
    for(i=0;i<n-1;i++){
        fscanf(fi,"%d%d",&q,&k);
        tati[k]=q;
    }
    max=-1;
    for(i=0;i<n-1;i++){
        j=i+2;
        dist=1;
        while(tati[j]!=1)
            {
                j=tati[j];
                dist++;
            }
        if(dist>max)
        {
            k=i;
            max=dist;
        }
    }
    k+=2;
    j=k;
    comun[1]++;
    dist=0;
    while(tati[j]!=0)
    {
        comun[j]++;
        distc[j]=dist;
        j=tati[j];
        dist++;
    }
    distc[1]=dist;
    max=-1;
    for(i=1;i<=n;i++){
        j=i;
        dist=0;
        while(comun[j]==0)
        {
            dist++;
            j=tati[j];
        }
        dist=dist+distc[j]+1;
        if(max<dist)
            max=dist;
    }
    fprintf(fo,"%d",max);
    fclose(fi);
    fclose(fo);
    return 0;
}