Cod sursa(job #2277496)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 6 noiembrie 2018 13:08:08
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define DIM 100005
using namespace std;

ifstream in("data.in");
ofstream out("data.out");

int n, a, b, maxi = -1;
vector<int> l[DIM];

queue<int> coada;
bool vizitat[DIM];
int ultim, nod;
int d[DIM];

int main()
{
    in>>n;
    for( int i = 1; i <= n; i++ )
    {
        in>>a>>b;
        l[a].push_back(b);
        l[b].push_back(a);
    }

    coada.push(1);
    vizitat[1] = true;

    while( !coada.empty() )
    {
        nod = coada.front();
        coada.pop();

        ultim = nod;

        for( unsigned int i = 0; i < l[nod].size(); i++ )
            if( vizitat[ l[nod][i] ] == 0 )
            {
                coada.push(l[nod][i]);
                vizitat[l[nod][i]] = 1;
            }
    }

    coada = queue<int>();
    coada.push(ultim);
    vizitat[ultim] = false;
    d[ultim] = 0;

    while( !coada.empty() )
    {
        nod = coada.front();
        coada.pop();

        for( unsigned int i = 0; i < l[nod].size(); i++ )
            if( vizitat[ l[nod][i] ] == 1 )
            {
                coada.push(l[nod][i]);
                d[l[nod][i]] = d[nod] + 1;
                vizitat[l[nod][i]] = 0;
            }
    }

    for( int i = 1; i <= n; i++ )
        maxi = max(maxi, d[i]);

    out<<maxi+1;

    return 0;
}