Cod sursa(job #2555444)

Utilizator andru47Stefanescu Andru andru47 Data 24 februarie 2020 04:30:52
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
vector <int> g[100005];
inline pair<int, int> bfs(int start, int vertices, int edges){
    queue< pair<int, int> > q;
    q.push({start, 0});
    bool ap[100005];
    for (int i = 0; i <= vertices; ++i)
        ap[i] = false;
    ap[start] = true;
    int maxy = 0, node = start;
    while(!q.empty()){
        int top = q.front().first;
        int distance = q.front().second;
        q.pop();
        for (auto &it : g[top]){
            if (!ap[it]){
                ap[it] = true;
                if (distance + 1 > maxy){
                    maxy = distance + 1;
                    node = it;
                }
                q.push({it, distance + 1});
            }
        }
    }
    return {maxy, node};
}
int main(){
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int vertices;
    cin >> vertices;
    //Read the edges and compute the neighbours for all vertices
    for (int i = 1; i<= vertices - 1; ++i){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cout << bfs(bfs(1, vertices, vertices - 1).second, vertices, vertices - 1).first + 1 << endl;
    return 0;
}