Cod sursa(job #3375952)

Utilizator mbazacliuMihnea Gabriel Bazacliu mbazacliu Data 14 noiembrie 2026 14:47:06
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

pair<int, int> fts(vector<vector<int>> G, int st){
    int n = G.size();

    vector<int> d(n);
    d[st] = 1;

    stack<int> s;
    s.push(st);

    int mx = st;
    while (!s.empty()){
        int u = s.top();

        while (!G[u].empty() && d[G[u].back()]) G[u].pop_back();
        if (G[u].empty()) s.pop();
        else {
            int v = G[u].back();
            G[u].pop_back();
            d[v] = d[u] + 1;
            if (d[v] > d[mx]) mx = v;
            s.push(v);
        }
    }

    return {mx, d[mx]};
}

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

    vector<vector<int>> G(n);
    for (int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;

        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    cout << fts(G, fts(G, 0).first).second;
}