Cod sursa(job #1378789)

Utilizator IgorDodonIgor Dodon IgorDodon Data 6 martie 2015 14:19:36
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define MAXN 100005
FILE *f=fopen("darb.in","r"), *g=fopen("darb.out","w");

using namespace std;

vector <int> v[MAXN];

long int N, L, U;

void Citire(){
long int i, x, y;

    fscanf(f,"%ld\n",&N);
    for(i=1;i<=N-1;i++){
        fscanf(f,"%ld %ld\n",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void BFS(long int nod){
long int Q[MAXN], k1, k2, viz[MAXN], i, nodnou, l[MAXN];

    for(i=1;i<=N;i++) viz[i]=0;

    Q[1]=nod; k1=1; k2=1; viz[nod]=1; l[1]=1;
    while( k1<=k2 ){

        nod = Q[k1];
        for(i=0;i<v[nod].size();i++){
            nodnou = v[nod][i];
            if( viz[nodnou]==0 ){ Q[++k2] = nodnou; l[k2] = l[k1]+1; viz[nodnou]=1; }
        }

        k1++;
    }
    L = l[k2]; U = Q[k2];

}

int main(){

    Citire();
    BFS(1);
    BFS(U);
    fprintf(g,"%ld\n",L);

return 0;
}