Cod sursa(job #2133196)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 16 februarie 2018 17:31:29
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("darb.in");
ofstream out ("darb.out");
int d[100001],far,n,x,y;
int coada[100001];
vector<int>v[100001];
void bfs (int nod) {
    coada[1] = nod;
    d[nod] = 1;
    for (int st = 1, dr = 1; st <= dr; st ++) {
        int knot = coada[st];
        for (int i = 0; i < v[knot].size(); i ++) {
            int vecin = v[knot][i];
            if (d[vecin] == 0) {
                d[vecin] = d[knot]+1;
                coada[++dr] = vecin;
            }
        }
    }
    return;
}
int main (void) {
    in >> n;
    for (int i = 1; i <= n - 1; i ++) {
        in >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }
    bfs (1);
    for (int i = 1; i <= n; i ++) {
        if (d[i] > d[far]) {
            far = i;
        }
    }
    for (int i = 1; i <= n; i ++) {
        d[i] = 0;
    }
    bfs (far);
    far = 0;
    for (int i = 1; i <= n; i ++) {
        if (d[i] > d[far]) {
            far = i;
        }
    }
    out << d[far];
    return 0;
}