Cod sursa(job #1333217)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 2 februarie 2015 21:48:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define MAXN 100005
FILE *f=fopen("darb.in","r"), *g=fopen("darb.out","w");

using namespace std;

long int N, viz[MAXN], q[MAXN], nr[MAXN], k1, k2;   // q = coada, nr = nr de noduri prin care a trecut
vector<int> v[MAXN];

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 Parcurgere( long int nod ){
long int i, nod1, nod2;

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

    k1=1; k2=1; viz[nod]=1; nr[1] = 1; q[1] = nod;

    while( k1<=k2 ){

        nod1 = q[k1];

        for( i=0; i<v[nod1].size(); i++ ){

            nod2 = v[nod1][i];

            if( viz[ nod2 ] == 0 ){
                viz[ nod2 ] = 1;
                k2++; q[k2]=nod2; nr[k2] = nr[k1] + 1;
            }

        }

        k1++;

    }

}

int main(){

    Citire();
    Parcurgere(1);
    Parcurgere( q[k2] );
    fprintf(g,"%ld\n",nr[k2]);

return 0;
}