Cod sursa(job #1547165)

Utilizator mihai.alphamihai craciun mihai.alpha Data 9 decembrie 2015 06:27:12
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
#include <stdlib.h>

int v[100001], a[100001];

void adinc(int noduri){
    if(a[noduri]==0){
        adinc(v[noduri]);
        a[noduri]=a[v[noduri]]+1;
    }
}

void lung(int noduri){
    if(v[noduri]!=0){
        lung(v[noduri]);
        v[v[noduri]]=noduri;
    }
}

int main()
{
    int n, i, rad, p, nod, maxim, nrmax;
    FILE*fin=fopen("darb.in","r"), *fout=fopen("darb.out","w");
    fscanf(fin,"%d", &n);
    for(i=2;i<=n;i++){
        fscanf(fin,"%d%d", &p, &nod);
        v[nod]=p;
    }
    for(i=1;i<=n;i++)
        if(v[i]==0)
            rad=i;

    a[rad]=1;
    maxim=-1;
    for(i=1;i<=n;i++){
        adinc(i);
        if(a[i]>maxim){
            maxim=a[i];
            nrmax=i;
        }
    }

    lung(nrmax);
    v[nrmax]=0;
    for(i=0;i<=n;i++)
        a[i]=0;

    maxim=-1;
    int nrmaxrasp;
    a[nrmax]=1;
    for(i=1;i<=n;i++){
        adinc(i);
        if(a[i]>maxim){
            maxim=a[i];
            nrmaxrasp=i;
        }
    }

    fprintf(fout,"%d", a[nrmaxrasp]);

    fclose(fin);
    fclose(fout);
    return 0;
}