Cod sursa(job #1602358)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 16 februarie 2016 18:56:58
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<cstring>
#include<vector>

using namespace std;

ifstream fin( "darb.in" ); ofstream fout( "darb.out" );

typedef vector< int > graf;

const int nmax = 1e5;
bool f[ nmax + 1 ];
graf g[ nmax + 1 ];

struct str{
    int nod, dist;

    str() {}
    str( int _x, int _y ) : nod( _x ), dist( _y ) {}
} q[ nmax + 1 ];

str ultimul_nod( int x ) {
    int first = 0, last = -1;
    str p;

    memset( f, 0, sizeof( f ) );
    f[ x ] = 1;
    q[ ++ last ] = str( x, 0 );

    while ( first <= last ) {
        p = q[ first ++ ];

        for( graf::iterator it = g[ p.nod ].begin(); it != g[ p.nod ].end(); ++ it ) {
            if ( f[ *it ] == 0 ) {
                f[ *it ] = 1;
                q[ ++ last ] = str( *it, p.dist + 1 );
            }
        }
    }
    return p;
}
int main() {
    int n;
    fin >> n;
    for( int i = 0; i < n - 1; ++ i ) {
        int x, y;
        fin >> x >> y;
        g[ x ].push_back( y );
        g[ y ].push_back( x );
    }
    fout << ultimul_nod( ultimul_nod( 1 ).nod ).dist + 1 << "\n";
    fin.close();
    fout.close();
    return 0;
}