Pagini recente » Cod sursa (job #1023404) | Cod sursa (job #2881428) | Cod sursa (job #895831) | Cod sursa (job #102206) | Cod sursa (job #1731654)
#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 ;
}