Cod sursa(job #3342554)

Utilizator MrPetcuPetcu Robert MrPetcu Data 24 februarie 2026 17:51:56
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <vector>
#include <fstream>

using namespace std;

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

int num_noduri;

int nod_1, nod_2;
vector<int> adiacenta[100000 + 5];

int distanta[100000 + 5];
int distanta_maxima;

int capat_1, capat_2;

void get_capat_1(int nod = 1){
    if(distanta[nod] > distanta_maxima){
        distanta_maxima = distanta[nod];
        capat_1 = nod;
    }

    for(int vecin : adiacenta[nod]){
        if(distanta[vecin] == 0){
            distanta[vecin] = distanta[nod] + 1;
            get_capat_1(vecin);
        }
    }
}

void get_capat_2(int nod = capat_1){
    if(distanta[nod] > distanta_maxima){
        distanta_maxima = distanta[nod];
        capat_2 = nod;
    }

    for(int vecin : adiacenta[nod]){
        if(distanta[vecin] == 0){
            distanta[vecin] = distanta[nod] + 1;
            get_capat_2(vecin);
        }
    }
}

void clear_distante(){
    distanta_maxima = 0;
    for(int i = 1; i <= num_noduri; i++){
        distanta[i] = 0;
    }
    distanta[capat_1] = 1;
}

int main(){
    fin >> num_noduri;
    for(int i = 1; i <= num_noduri - 1; i++){
        fin >> nod_1 >> nod_2;
        adiacenta[nod_1].push_back(nod_2);
        adiacenta[nod_2].push_back(nod_1);
    }

    get_capat_1();
    clear_distante();
    get_capat_2();

    fout << distanta_maxima;

    return 0;
}