Cod sursa(job #2841079)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 29 ianuarie 2022 11:45:13
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;
#ifdef INFOARENA
#define cin fin
#define cout fout
ifstream fin("darb.in");
ofstream fout("darb.out");
#endif // INFOARENA
const int NMAX = 3e5;
int n, x, y;
vector <int> d;
vector <vector <int>> g;
void bfs(int root) {
    d.resize(n + 1, -1);
    queue <int> q;
    q.push(root); d[root] = 0;
    while(!q.empty()) {
        int top = q.front();
        q.pop();
        for(int adj : g[top])
            if(d[adj] == -1)
                d[adj] = 1 + d[top],
                q.push(adj);
    }
}

void Input() {
    cin >> n; g.resize(n + 1);
    for(int i = 1; i < n; i++)
        cin >> x >> y,
        g[x].push_back(y),
        g[y].push_back(x);
}

void Solve() {
    bfs(1);
    int maxd = -1, last = 0;
    for(int i = 1; i <= n; i++)
        if(d[i] > maxd)
            maxd = d[i],
            last = i;
    d.clear();
    bfs(last);
    for(int i = 1; i <= n; i++)
        maxd = max(maxd, d[i]);
    cout << maxd + 1 << "\n";
}

int main() {
    Input();
    Solve();
    return 0;
}