Cod sursa(job #2708830)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 19 februarie 2021 15:00:13
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 1e5;
vector < int > g[NMAX + 1];
FILE *fin;
ofstream fout ( "darb.out" );
int get () {
    int nr = 0, ch;
    while ( !isdigit ( ch = fgetc ( fin ) ) );
    do {
        nr = nr * 10 + ch - '0';
    } while ( isdigit ( ch = fgetc ( fin ) ) );
    return nr;
}
int dist[NMAX + 1];
int n;
void bfs ( int start ) {
    for ( int i = 1; i <= n; i++ )
        dist[i] = 0;
    int curr;
    queue < int > q;
    q.push ( start );
    dist[start] = 1;
    while ( q.size() > 0 ) {
        curr = q.back();
        q.pop();
        for ( auto x: g[curr] )
            if ( dist[x] == 0 ) {
                dist[x] = dist[curr] + 1;
                q.push ( x );
            }
    }
}
int main () {
    int x, y, maxy, node;
    fin = fopen ( "darb.in", "r" );
    n = get();
    for ( int i = 1; i < n; i++ ) {
        x = get ();
        y = get ();
        g[x].push_back ( y );
        g[y].push_back ( x );
    }
    fclose ( fin );
    bfs ( 1 );
    maxy = -1;
    for ( int i = 1; i <= n; i++ )
        if ( dist[i] > maxy ) {
            maxy = dist[i];
            node = i;
        }
    bfs ( node );
    maxy = -1;
    for ( int i = 1; i <= n; i++ )
        maxy = ( dist[i] > maxy? dist[i] : maxy );
    fout << maxy + 1;
    
    return 0;
}