Cod sursa(job #3265217)

Utilizator not_anduAndu Scheusan not_andu Data 28 decembrie 2024 10:26:14
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "darb.in"
#define OUTFILE "darb.out"

const int N_MAX = 1e5;

int nodes;
int d[N_MAX + 5];
vector<int> adj[N_MAX + 5];

void bfs(int source){

    for(int i = 1; i <= nodes; ++i) d[i] = 0;

    d[source] = 1;
    queue<int> q; q.push(source);

    while(!q.empty()){
        int node = q.front(); q.pop();
        for(auto &to : adj[node]){
            if(!d[to]){
                d[to] = d[node] + 1;
                q.push(to);
            }
        }
    }

}

void debug(int v[]){
    for(int i = 1; i <= nodes; ++i){
        cerr << v[i] << " ";
    }
    cerr << '\n';
}

void solve(){

    cin >> nodes;
    for(int i = 1; i < nodes; ++i){
        int node, to; cin >> node >> to;
        adj[node].push_back(to);
        adj[to].push_back(node);
    }

    bfs(1);

    int start = -1, lenMax = -1;
    for(int i = 1; i <= nodes; ++i){
        if(d[i] > lenMax){
            lenMax = d[i];
            start = i;
        }
    }

    bfs(start);

    int ans = -1;
    for(int i = 1; i <= nodes; ++i){
        ans = max(ans, d[i]);
    }

    cout << ans << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    solve();
    return 0;
}