Cod sursa(job #1403517)

Utilizator BLz0rDospra Cristian BLz0r Data 27 martie 2015 12:48:31
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

#define Nmax 100002
#define inf 0x3f3f3f3f
#define pb push_back

FILE *f = fopen ( "darb.in", "r" );
FILE *g = fopen ( "darb.out", "w" );

vector < int > G[Nmax];
queue < int > Q;
int dist[Nmax], Nod, N;

int BFS ( int start ){
    vector < int > :: iterator it;
    memset ( dist, inf, sizeof(dist) );

    Q.push ( start );
    dist[start] = 0;

    while ( !Q.empty() ){
        int nod = Q.front();
        Q.pop();

        for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
            if ( dist[*it] == inf ){
                dist[*it] = dist[nod] + 1;
                Q.push ( *it );
            }
        }
    }

    int maxdist = -1;

    for ( int i = 1; i <= N; ++i )
        if ( maxdist < dist[i] ){
            maxdist = dist[i];
            Nod = i;
        }
    return maxdist;
}

int main(){
    int x, y;

    fscanf ( f, "%d", &N );

    for ( int i = 1; i < N; ++i ){
        fscanf ( f, "%d%d", &x, &y );
        G[x].pb ( y );
        G[y].pb ( x );
    }

    BFS ( 1 );

    fprintf ( g, "%d", BFS ( Nod ) + 1 );

    return 0;
}