Cod sursa(job #3330362)

Utilizator Alex283810Mocan Alexandru Vali Alex283810 Data 18 decembrie 2025 22:47:45
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <string>
#include <queue>

std::vector<std::vector<int>>graph;

int dist[100001];

void bfs(int x)
{
    std::queue<int>q;
    q.push(x);
    dist[x] = 0;
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();
        if(graph[curr].size() == 0)continue;
        for(auto h : graph[curr])
        {
            if(dist[h] == -1)
            {
                //std::cout << h << ' ';
                dist[h] = dist[curr] + 1;
                q.push(h);
            }
        }
    }
}
int main() {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    int n;
    std::cin >> n;

    graph.resize(n + 1);

    for(int i = 1; i <= n; i++)
        dist[i] = -1;

    for(int i = 1; i <= n - 1; i++)
    {
        int a, b;
        std::cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    bfs(1);

    int maxi1 = INT_MIN, nod1 = 0;

    for(int i = 1; i <= n; i++)
    {
        if(maxi1 < dist[i])
        {
            maxi1 = dist[i]; nod1 = i;
        }
    }

    for(int i = 1;  i <= n; i++)
        dist[i] = -1;

    bfs(nod1);

    maxi1 = INT_MIN;

    for(int i = 1; i <= n; i++)
    {
        if(maxi1 < dist[i])
        {
            maxi1 = dist[i]; nod1 = i;
        }
    }

    std::cout << maxi1 + 1;
    return 0;
}