Cod sursa(job #1987751)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 31 mai 2017 22:35:28
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>

#define ll long long
#define pb push_back

using namespace std;

 ifstream fin("darb.in");
ofstream fout("darb.out");


const int NLIM = 1e5 + 10;

int N;
vector< int > graph[NLIM];

int bfs( int ST, int& rnod, int& rl )
{
    int bfsv[NLIM];
    for( int i = 1; i <= N; ++i )
        bfsv[i] = 0;

    queue< int > qu;
    bfsv[ST] = 1;
    qu.push( ST );

    rl = -1;
    while( qu.size() )
    {
        int nod = qu.front();
        for( int j = 0; j < graph[nod].size(); ++j )
        {
            int nnod = graph[nod][j];
            if( !bfsv[nnod] )
            {
                bfsv[nnod] = bfsv[nod] + 1;

                qu.push( nnod );

                if( bfsv[nnod] > rl )
                {
                    rl = bfsv[nnod];
                    rnod = nnod;
                }
            }
        }
        qu.pop();
    }
}

int main()
{
    fin >> N;
    for( int i = 0; i < N - 1; ++i )
    {
        int x, y;
        fin >> x >> y;
        graph[x].push_back( y );
        graph[y].push_back( x );
    }

    int res;
    int ST2;

    bfs( 1, ST2, res );
    bfs( ST2, ST2, res );

    fout << res;


    return 0;
}