Cod sursa(job #3227371)

Utilizator Luijika_programatorulBursuc Luigi Luijika_programatorul Data 29 aprilie 2024 23:04:59
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include<bits/stdc++.h>
auto in = std::freopen("darb.in" , "r" , stdin);
auto out = std::freopen("darb.out" , "w" , stdout);
const int NMAX = 100005;
std::vector<int> g[NMAX];
int n;
std::vector<int> bfs(int nod){
    std::queue<int> q;
    std::vector<int> rasp(n+1,INT_MAX);
    q.push(nod);
    rasp[nod]=0;
    while(q.size()){
        int cnod = q.front();
        q.pop();
        for(auto f : g[cnod]){
            if(rasp[f] == INT_MAX){
                q.push(f);
                rasp[f] = rasp[cnod] + 1;
            }
        }
    }
    return rasp;
}
int main(){
    std::cin >> n;
    for(int i=1,u,v;i<n;++i){
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto d1 = bfs(1);
    std::pair<int,int> c1 = {0,0};
    for(int i=1;i<=n;++i){
        c1 = std::max(c1, {d1[i] , i});
    }
    d1 = bfs(c1.second);
    int rasp=0;
    for(int i=1;i<=n;++i){

        rasp = std::max(rasp,d1[i]);
    }
    std::cout << rasp + 1;
    return 0;
}