Cod sursa(job #2049354)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 27 octombrie 2017 09:07:49
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ofstream fout ("darb.out");
ifstream fin ("darb.in");
int n,rsp,lungmax,aux,i,a,b;
int dist[100005];
vector < int > v[100005];
queue < int > q;
void bfs( int nod )
{
    memset( dist , 0 , sizeof( dist ) );
    q.push( nod );
    dist[ nod ] = 1;
    while( q.size() )
    {
        aux = q.front();
        q.pop();
        for( auto it : v[ aux ] )
        {
            if( !dist[ it ] )
            {
                dist[ it ] = dist[ aux ] + 1;
                q.push( it );
            }
        }
    }
    for( i = 1 ; i <= n ; i++ )
    {
        if( dist[ i ] > lungmax )
        {
            lungmax = dist[ i ];
            rsp = i;
        }
    }
}
int main()
{
    fin>>n;
    for( i = 1 ; i < n ; i++ )
    {
        fin>>a>>b;
        v[ a ].push_back( b );
        v[ b ].push_back( a );
    }
    bfs( 1 );
    bfs( rsp );
    fout<<lungmax;
    return 0;
}