Cod sursa(job #2601196)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 14 aprilie 2020 00:16:46
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f ( "darb.in" );
ofstream g ( "darb.out" );
vector <int> v[100002];
int dist[100002];
queue<int>Q;
void BFS ( int x )
{
    dist[x] = 1;
    Q.push ( x );

    while ( !Q.empty() )
    {
        int crt = Q.front();
        Q.pop();

        for ( vector<int>::iterator k = v[crt].begin(); k != v[crt].end(); ++k )
        {
            int vec = *k;

            if ( dist[vec] == 0 )
            {
                dist[vec] = dist[crt] + 1;
                Q.push ( vec );
            }
        }
    }
}
int main()
{
    int N, x, y;
    f >> N;

    for ( int i = 1; i < N; i++ )
    {
        f >> x >> y;
        v[x].push_back ( y );
        v[y].push_back ( x );
    }

    BFS ( 1 );
    int mx = 0, poz;

    for ( int i = 1; i <= N; i++ )
    {
        if ( dist[i] > mx )
        {
            mx = dist[i];
            poz = i;
        }

        dist[i] = 0;
    }

    BFS ( poz );
    mx = 0;

    for ( int i = 1; i <= N; i++ )
        if ( dist[i] > mx )
            mx = dist[i];
    g << mx;
    return 0;
}