Cod sursa(job #1467694)

Utilizator CollermanAndrei Amariei Collerman Data 3 august 2015 22:26:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ofstream fout("darb.out");
ifstream fin("darb.in");

const int NMAX = 100005;

int n, last_idx, last;
int Nivel[NMAX];
vector<int> Graf[NMAX];
queue<int> Q;

void bfs(int first)
{
    last_idx = 0;
    for(int i=1; i<=n-1; i++) Nivel[i] = 0;
    Nivel[first] = 1;
    Q.push(first);

    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();

        for(auto x : Graf[nod]) {
            if(!Nivel[x]) {
                Nivel[x] = Nivel[nod] + 1;
                Q.push(x);

                if(Nivel[x] > last_idx) {
                     last_idx = Nivel[x];
                     last = x;
                }
            }
        }
    }
}

int main()
{
    fin >> n;
    for(int i=1, x, y; i<=n-1; i++) {
        fin >> x >> y;
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }

    bfs(1);
    bfs(last);
    fout << last_idx << '\n';
    return 0;
}