Cod sursa(job #1127158)

Utilizator mvcl3Marian Iacob mvcl3 Data 27 februarie 2014 11:24:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <set>

#define in "darb.in"
#define out "darb.out"
#define Max_Size 100009
#define oo 10000000

std :: ifstream f(in);
std :: ofstream g(out);

int N, D[Max_Size], NOD, minim;
std :: vector < int > V[Max_Size];
std :: set < std :: pair < int, int > > H;

void DFS(int nod) {
   for(auto val : V[nod]) {
        if(D[val] > D[nod] + 1) {
            D[val] = D[nod] + 1;

            if(minim < D[val]) {
                NOD = val;
                minim = D[nod];
            }

            DFS(val);
        }
   }
}

int main() {
    f >> N;
    for(int x, y, i = 1; i < N; ++i) {
        f >> x >> y;

        V[x].push_back(y);
        V[y].push_back(x);
    }

    for(int i = 1; i <= N; ++i) D[i] = oo;
    D[1] = 0;
    DFS(1);

    for(int i = 1; i <= N; ++i) D[i] = oo;
    D[NOD] = 1, minim = 0;
    DFS(NOD);

    g << minim + 1 << '\n';

    g.close();
    return 0;
}