Pagini recente » Cod sursa (job #2072803) | Cod sursa (job #350692) | Cod sursa (job #1538109) | Cod sursa (job #513433) | Cod sursa (job #1268208)
#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 ;
}