Cod sursa(job #1127146)

Utilizator mvcl3Marian Iacob mvcl3 Data 27 februarie 2014 11:21:49
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 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 DJKSTR(int nod) {
    H.insert( {0, nod } );
    minim = 0;

    while(!H.empty()) {
        std :: pair < int, int > x = *H.begin();
        H.erase( *H.begin() );

        for(auto val : V[x.second]) {
            if(D[val] > x.first + 1) {
                D[val] = x.first + 1;
                H.insert( {D[val], val} );

                if(D[val] > minim) {
                    minim = D[val];
                    NOD = 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;
    DJKSTR(1);

    for(int i = 1; i <= N; ++i) D[i] = oo;
    D[NOD] = 1;
    DJKSTR(NOD);

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

    g.close();
    return 0;
}