Cod sursa(job #2814043)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 7 decembrie 2021 14:46:50
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>

#define MAX 100000

int dp[ MAX ], n;
bool ok[ MAX ];

std::vector<int> nod[ MAX ];
std::queue<int> q;

int dr, d;
void bfs( int st ) {
    memset( dp, 0, MAX );
    memset( ok, 0, MAX );

    q.push( st );

    dp[ st ] = 1;
    ok[ st ] = true;
    while( !q.empty() ) {
        int el = q.front();
        q.pop();

        for( int i = 0; i < nod[ el ].size(); i++ )
            if( !ok[ nod[ el ][ i ] ] ) {
                q.push( nod[ el ][ i ] );
                ok[ nod[ el ][ i ] ] = true;
                dp[ nod[ el ][ i ] ] = dp[ el ] + 1;

                d = dp[ nod[ el ][ i ] ];
                dr = nod[ el ][ i ];
            }
    }
}

int main()
{
    FILE *fin = fopen( "darb.in", "r" );
    fscanf( fin, "%d", &n );

    int x, y;
    for( int i = 0; i < n; i++ ) {
        fscanf( fin, "%d%d", &x, &y );
        nod[ x ].push_back( y );
        nod[ y ].push_back( x );
    }
    fclose( fin );

    bfs( 1 );
    bfs( dr );

    FILE *fout = fopen( "darb.out", "w" );
    fprintf( fout, "%d\n", d );
    fclose( fout );
    return 0;
}