Cod sursa(job #2749426)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 6 mai 2021 17:41:33
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <deque>
#include <stack>
#include <algorithm>

using namespace std;
ifstream cin("darb.in") ;
ofstream cout("darb.out") ;

int n ;

vector<int> v[100009] ;

int pasi[100009] ;

int lee(int x)
{

    deque<int> dq ;

    dq.push_back(x) ;

    pasi[x] = 1 ;

    while(dq.size())
    {

        int curent = dq.front() ;

        dq.pop_front() ;

        for(int f = 0 ; f < v[curent].size() ; f ++)
            if(!pasi[v[curent][f]])pasi[v[curent][f]] = pasi[curent] + 1, dq.push_back(v[curent][f]) ;

    }

    int mx = 0, mxnod = 1 ;

    for(int f = 1 ; f <= n ; f ++)
        if(pasi[f] > mx)
        {

            mx = pasi[f] ;

            mxnod = f ;

        }

    return mxnod ;

}

int pasi2[100009] ;

int lee2(int x)
{

    deque<int> dq ;

    dq.push_back(x) ;

    pasi2[x] = 1 ;

    while(dq.size())
    {

        int curent = dq.front() ;

        dq.pop_front() ;

        for(int f = 0 ; f < v[curent].size() ; f ++)
            if(!pasi2[v[curent][f]])pasi2[v[curent][f]] = pasi2[curent] + 1, dq.push_back(v[curent][f]) ;

    }

    int mx = 0, mxnod = 1 ;

    for(int f = 1 ; f <= n ; f ++)
        if(pasi2[f] > mx)
        {

            mx = pasi2[f] ;

            mxnod = f ;

        }

    return mxnod ;

}

int main()
{

    cin >> n ;

    for(int f = 1 ; f < n ; f ++)
    {

        int a, b ;

        cin >> a >> b ;

        v[a].push_back(b) ;
        v[b].push_back(a) ;

    }

    cout << pasi2[lee2(lee(1))] ;

    return 0;
}