Cod sursa(job #2593034)

Utilizator nTropicManescu Bogdan Constantin nTropic Data 2 aprilie 2020 19:20:51
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

const int len = 100005;
int n, x, y, max_dist, max_node;
vector<int> g[len];
vector<bool> seen(len, false);

void dfs(int node, int dist) {
    if (max_dist < dist) {
        max_dist = dist;
        max_node = node;
    }

    seen[node] = true;
    for (int& it : g[node])
        if (!seen[it])
            dfs(it, dist + 1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    cin >> n;
    while (--n) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, 1);
    seen.assign(len, false);
    dfs(max_node, 1);

    cout << max_dist;
}