Cod sursa(job #2744537)

Utilizator Tudor06MusatTudor Tudor06 Data 24 aprilie 2021 20:11:54
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

const int NMAX = 1e5;

bool viz[NMAX + 1];

vector <int> edge[NMAX + 1];
deque <pair<int, int>> dq;

void reset() {
    for ( int i = 0; i <= NMAX; i ++ ) {
        viz[i] = false;
    }
}
void bfs( int node, int& ans, int& dist ) {
    int d;
    dist = ans = 0;
    dq.push_back( { node, 1 } );
    while ( !dq.empty() ) {
        node = dq.front().first;
        d = dq.front().second;
        if ( d > dist ) {
            dist = d;
            ans = node;
        }
        dq.pop_front();
        for ( auto& nb : edge[node] ) {
            if ( !viz[nb] ) {
                dq.push_back( { nb, d + 1 } );
                viz[nb] = true;
            }
        }
    }
    reset();
}
int main() {
    ifstream fin( "darb.in" );
    ofstream fout( "darb.out" );

    int n, a, b, node, dist;
    fin >> n;
    for ( int i = 1; i < n; i ++ ) {
        fin >> a >> b;
        edge[a].push_back( b );
        edge[b].push_back( a );
    }

    bfs( 1, node, dist );
    bfs( node, a, dist );
    fout << dist;
    return 0;
}