Cod sursa(job #3285760)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 13 martie 2025 14:14:08
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int N = 1e5;
int dist[N + 1];

vector <int> g[N + 1];

int n, x, y, frunza, mx;

void bfs (int node)
{
   for (int i = 1; i <= n; ++i)
        dist[i] = 0;
    queue <int> q;
    q.push(node);
    dist[node] = 1;
    mx = 0;
    while (!q.empty())
    {
        int x = q.front();
        if (mx < dist[x])
            mx = dist[x], frunza = x;
        q.pop();
        for (auto it : g[x])
            if (!dist[it])
                dist[it] = dist[x] + 1, q.push(it);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs (1);
    bfs (frunza);
    cout << mx << '\n';
    return 0;
}