Cod sursa(job #2708852)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 19 februarie 2021 15:22:56
Problema Diametrul unui arbore Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#define N 100000
#define NQ 131072

using namespace std;

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

vector <int> g[N + 1];
int lungime[N + 1];
int n;
int coada[NQ];
int prim, ultim;

void bfs( int nod ) {
    lungime[nod] = 1;
    coada[ultim] = nod;
    ultim = ( ultim + 1 ) % NQ;
    do {
        nod = coada[prim];
        prim = ( prim + 1 ) % NQ;
        for ( int i = 0; i < g[nod].size(); i ++ ) {
            if ( lungime[g[nod][i]] == 0 ) {
                coada[ultim] = g[nod][i];
                ultim = ( ultim + 1 ) % NQ;
                lungime[g[nod][i]] = lungime[nod] + 1;
            }
        }
    } while ( prim < ultim );
}

int main() {
    int x, y, maxx, nod;
    fin >> n;
    while ( !fin.eof() ) {
        fin >> x >> y;
        g[x].push_back( y );
        g[y].push_back( x );
    }

    bfs( 1 );
    maxx = 0;
    nod = 0;
    for ( int i = 1; i <= n; i ++ ) {
        if ( lungime[i] > maxx ) {
            maxx = lungime[i];
            nod = i;
        }
        lungime[i] = 0;
    }

    bfs( nod );
    maxx = 0;
    nod = 0;
    for ( int i = 1; i <= n; i ++ ) {
        if ( lungime[i] > maxx ) {
            maxx = lungime[i];
            nod = i;
        }
    }
    fout << maxx << "\n";
    return 0;
}