Cod sursa(job #1547029)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 8 decembrie 2015 22:05:25
Problema Diametrul unui arbore Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>
#include <stdlib.h>

int v[10001], d[10001];

void depth(int nod){
    if(d[nod]==0){
        depth(v[nod]);
        d[nod]=d[v[nod]]+1;
    }
}

void turn(int nod){
    if(v[nod]!=0){
        turn(v[nod]);
        v[v[nod]]=nod;
    }
}

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

    d[root]=1;
    max=-1;
    for(i=1;i<=n;i++){
        depth(i);
        if(d[i]>max){
            max=d[i];
            nrmax=i;
        }
    }

    turn(nrmax);
    v[nrmax]=0;
    for(i=0;i<=n;i++)
        d[i]=0;

    max=-1;
    int nrmax2;
    d[nrmax]=1;
    for(i=1;i<=n;i++){
        depth(i);
        if(d[i]>max){
            max=d[i];
            nrmax2=i;
        }
    }

    fprintf(fo,"%d", d[nrmax2]);

    fclose(fi);
    fclose(fo);
    return 0;
}