Cod sursa(job #3365425)

Utilizator andrei_obrejaAndrei Obreja andrei_obreja Data 21 septembrie 2026 10:04:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("darb.in");
ofstream fout ("darb.out");
vector<vector<int>> g;
int diam=0;
int bfs(int start, int &last, int n)
{
    queue<int> q;
    int maxdist = 0;
    vector<int> dist(n + 1, -1);
    q.push(start);
    dist[start] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto v : g[u])
        {
            if(dist[v] == -1){
                q.push(v);
                dist[v] = dist[u] + 1;
                if(dist[v] > maxdist)
                    maxdist = dist[v], last = v;

            }
        }
    }
    return maxdist;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    fin >> n;
    g.resize(n  +1);
    for(int i = 1; i<= n - 1; i++)
    {
        int u,v;
        fin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int Y;
    bfs(1, Y, n);
    int Z, X;
    diam = bfs(Y, X, n);
    fout << diam + 1<< '\n';
    return 0;
}