Cod sursa(job #1541825)

Utilizator felixiPuscasu Felix felixi Data 4 decembrie 2015 16:31:08
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

const int NMAX = 100000;

int N, Ans, ad[NMAX+2], bf[NMAX+2], my_special_nod = 1, my_val = 1;
queue <int> Q;
vector <int> G[NMAX+2];

void DFS( int nod, int lay ) {
    ad[nod] = lay;
    if( lay > my_val ) {
        my_val = lay;
        my_special_nod = nod;
    }

    for( int i = 0;  i < (int)G[nod].size();  ++i ) {
        int x = G[nod][i];
        if( !ad[x] ) {
            DFS( x, lay+1 );
        }
    }
}

void BFS( int sursa ) {
    Q.push( sursa );
    bf[sursa] = 1;
    while( !Q.empty() ) {
        int nod = Q.front();
        Q.pop();

        for( int i = 0;  i < (int)G[nod].size();  ++i ) {
            int x = G[nod][i];
            if( !bf[x] || bf[nod] + 1 < bf[x] ) {
                bf[x] = bf[nod] + 1;
                Q.push( x );
            }
        }
    }
}

int main() {
    in >> N;
    for( int i = 1;  i < N;  ++i ) {
        int x,y;
        in >> x >> y;
        G[x].push_back( y );
        G[y].push_back( x );
    }
    DFS( 1, 1 );
    BFS( my_special_nod );
    for( int i = 1;  i <= N;  ++i ) {
        Ans = max( Ans, bf[i] );
    }
    out << Ans << '\n';
    return 0;
}