Cod sursa(job #3144241)

Utilizator SSKMFSS KMF SSKMF Data 6 august 2023 16:34:59
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector <int> adiacenta[100001];
int diferenta_maxima;

int Parcurgere (const int tata , const int nod_actual , const int adancime)
{
    int maxim[2] = {adancime , adancime - 1};
    for (auto nod_vecin : adiacenta[nod_actual])
        if (nod_vecin != tata)
        {
            const int adancime_nod_vecin = Parcurgere(nod_actual , nod_vecin , adancime + 1);
            if (adancime_nod_vecin > maxim[0])
                maxim[1] = maxim[0] , maxim[0] = adancime_nod_vecin;
            else
                if (adancime_nod_vecin > maxim[1])
                    maxim[1] = adancime_nod_vecin;
        }

    diferenta_maxima = max(diferenta_maxima , maxim[0] + maxim[1] - 2 * adancime + 1);
    return maxim[0];
}

int main ()
{
    int noduri;
    cin >> noduri;

    for (int indice = 1 , nod[2] ; indice < noduri ; indice++)
        { cin >> nod[0] >> nod[1]; adiacenta[nod[0]].emplace_back(nod[1]); adiacenta[nod[1]].emplace_back(nod[0]); }

    Parcurgere(0 , 1 , 0);
    cout << diferenta_maxima;
    cout.close(); cin.close();
    return 0;
}