Cod sursa(job #1930347)

Utilizator andru47Stefanescu Andru andru47 Data 18 martie 2017 19:29:07
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
int n ;
const int NMAX = 1e5 + 5;
vector <int> g[NMAX];
queue < pair<int , int> > q;
bool ok[NMAX];
inline pair<int , int> bfs(int nod)
{
    int maxy = 0 ,node = 1;
    q.push({nod , 0});
    for (int i = 1; i<=n; ++i)
        ok[i] = false;
    while(!q.empty())
    {
        pair<int , int> X = q.front();
        q.pop();
        ok[X.f] = true;
        if (X.s > maxy)maxy = X.s , node = X.f;
        for (auto &it : g[X.f])
            if (!ok[it])
                q.push({it , X.s + 1});
    }
    return {maxy , node};
}
int main()
{
    freopen("darb.in" , "r", stdin);
    freopen("darb.out" , "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i<=n; ++i)
    {
        int x , y;
        scanf("%d %d\n", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    printf("%d\n", bfs(bfs(1).second).first + 1);
    return 0;
}