Cod sursa(job #1731654)

Utilizator jurjstyleJurj Andrei jurjstyle Data 19 iulie 2016 14:24:34
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std ;

ifstream f("darb.in") ;
ofstream g("darb.out") ;


vector <int> G[100005] , viz , dist ;
queue <int> Q ;
int N , ultim , dist_max ;


int main ()
{
 f >> N ;
 viz.resize ( N + 1 ) , dist.resize ( N + 1 ) ;
 int x , y ;
 while ( f >> x >> y )
    G[x].push_back (y) , G[y].push_back (x) ;

 //BFS din 1
 Q.push ( 1 ) , viz[1] = 1 , dist[1] = 0 ;
 while ( Q.empty () == 0 )
    {
     int nod_curent = Q.front () ;
     Q.pop() ;
     for ( vector <int> :: iterator I = G[nod_curent].begin() ; I < G[nod_curent].end () ; ++I )
        if ( viz[*I] == 0 )
            {
             viz[*I] = 1 ;
             Q.push ( *I ) ;
             dist[*I] = dist[nod_curent] + 1 ;
             ultim = *I ;
            }
    }
 //Acum facem BFS din ultim ( cea mai indepartata frunza )
 for ( int i = 1 ; i <= N ; ++i )
    viz[i] = dist[i] = 0 ;
 Q.push ( ultim ) , viz[ultim] = 1 , dist[ultim] = 0 ;
 while ( Q.empty () == 0 )
    {
     int nod_curent = Q.front () ;
     Q.pop() ;
     for ( vector <int> :: iterator I = G[nod_curent].begin() ; I < G[nod_curent].end () ; ++I )
        if ( viz[*I] == 0 )
            {
             viz[*I] = 1 ;
             Q.push ( *I ) ;
             dist[*I] = dist[nod_curent] + 1 ;
             dist_max = max ( dist_max , dist[*I] ) ;
            }
    }
 g << dist_max + 1 ;
}