Cod sursa(job #1268208)

Utilizator AndreiBarbutaAndrei Barbuta AndreiBarbuta Data 20 noiembrie 2014 18:39:08
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <queue>

#define pb push_back
#define p push

#define IN "darb.in"
#define OUT "darb.out"

const int MAX = 1000014 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

vector < int  > gr [ MAX ] ;
queue < int > q ;

int viz [ MAX ] , nr  [ MAX ] , last , diam , n ;

void bfs ( int nod ) ;

int main()
{
    fin >> n ;
    for ( register int  i = 1 ; i < n ; ++ i ){
        int x , y ;
        fin >> x >> y ;
        gr [ x ].pb ( y ) ;
        gr [ y ].pb ( x ) ;
    }
    bfs ( 1 ) ;
    bfs ( last ) ;
    fout << diam ;
    return 0;
}

void bfs ( int nod ) {
    q.p ( nod ) ;
    viz [ nod ] = 1 ;
    nr [ nod ] = 1 ;
    while ( !q.empty (  ) ){
        int x = q.front (  ) ;
        for ( int it = 0 ; it < gr [ x ].size ( ) ; ++ it )
            if ( !viz [ gr [ x ] [ it ] ] ){
                q.p ( gr [ x ] [ it ] ) ;
                nr [ gr [ x ] [ it ] ] = nr [ x ] + 1 ;
                viz [ gr [ x ] [ it ] ] = 1 ;
                last = gr [ x ] [ it ] ;
                diam = nr [ gr [ x ] [ it ] ] ;
            }
        q.pop (  ) ;
    }
    for ( register int i = 1 ; i <= n ; ++ i )
        viz [ i ] = nr [ i ] = 0 ;
}