Cod sursa(job #2442415)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 23 iulie 2019 21:23:57
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("darb.in");
ofstream fout ("darb.out");

vector <int> a[100005];
queue <int> q;
int d[100005], f[100005];
void bfs(int k)
{
    d[k] = 1;
    f[k] = 1;
    q.push(k);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(auto v : a[x])
            if(!f[v]) f[v] = 1, q.push(v), d[v] = d[x] + 1;
    }
}
int main()
{
    int n, x, y;
    fin >> n;
    while(fin >> x >> y) {
        a[x].push_back(y);
        a[y].push_back(x);
    }
    bfs(1);
    int mx = 0, pos;
    for(int i = 1; i <= n; ++i) {
        if(d[i] > mx) pos = i;
        mx = max(mx, d[i]);
    }
    memset(d, 0, sizeof(d));
    memset(f, 0, sizeof(f));
    bfs(pos);
    for(int i = 1; i <= n; ++i) {
        if(d[i] > mx) pos = i;
        mx = max(mx, d[i]);
    }
    fout << mx;
    return 0;
}