Cod sursa(job #1504954)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 18 octombrie 2015 16:34:39
Problema Diametrul unui arbore Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
int v[MAXN],next[MAXN],ind[MAXN+1],con=1,cod[MAXN],dist[2][MAXN+1];
inline void add(int x,int y){
    v[con]=x;
    next[con]=ind[y];
    ind[y]=con;
    con++;
}
inline void BFS(int nod,int i){
    int poz,b,e;
    cod[0]=nod;
    b=e=0;
    do{
        poz=ind[cod[b]];
        while(poz){
            if(dist[i][v[poz]]==0){
                dist[i][v[poz]]=dist[i][cod[b]]+1;
                cod[++e]=v[poz];
            }
            poz=next[poz];
        }
        b++;
    }while(b<=e);
}
int main(){
    FILE*fi,*fout;
    int i,n,max,x,y,poz;
    fi=fopen("darb.in" ,"r");
    fout=fopen("darb.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=0;i<n-1;i++){
       fscanf(fi,"%d%d" ,&x,&y);
       add(x,y);
       add(y,x);
    }
    BFS(1,0);
    max=0;
    for(i=1;i<=n;i++)
        if(dist[0][i]>max){
            max=dist[0][i];
            poz=i;
        }
    BFS(poz,1);
    max=0;
    for(i=1;i<=n;i++)
       if(max<dist[1][i])
           max=dist[1][i];
    fprintf(fout,"%d" ,max+1);
    fclose(fi);
    fclose(fout);
    return 0;
}