Cod sursa(job #1705203)

Utilizator CTI_KnightCir Constantin CTI_Knight Data 20 mai 2016 01:24:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
// FMI - UNIBUC - INFO
/*
    _|_|_|_|  _|_|_|_|_|  _|_|     _|  _|_|_|_|  _|_|_|_|_|     _|       _|_|     _|  _|_|_|_|_|  _|  _|_|     _|
    _|        _|      _|  _| _|    _|  _|            _|       _| _|      _| _|    _|      _|      _|  _| _|    _|
    _|        _|      _|  _|  _|   _|  _|            _|      _|   _|     _|  _|   _|      _|      _|  _|  _|   _|
    _|        _|      _|  _|   _|  _|    _|_|_|      _|     _| _|_|_|    _|   _|  _|      _|      _|  _|   _|  _|
    _|        _|      _|  _|    _| _|        _|      _|    _|       _|   _|    _| _|      _|      _|  _|    _| _|
    _|_|_|_|  _|_|_|_|_|  _|     _|_|  _|_|_|_|      _|   _|         _|  _|     _|_|      _|      _|  _|     _|_|

*/
// Platform: Infoarena
// Problem: Diametrul unui arbore
// Programming Language: C++
// Date: 20.5.2016

# include <fstream>
# include <algorithm>
# include <cstring>
# include <vector>
# include <queue>

using namespace std;

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

int n, answer, d_max; // n - numarul de noduri, answer - ..., d_max - extremitate
int vec[100005]; // vector de distante
vector < int > v[100005]; // v - retinem arborele
queue < int > q;    // coada pentru BFS

void distanta ( int start ) { // folosim BFS

    memset( vec, 0, sizeof( vec ) );

    answer = 0;
    vec[start] = 1;
    q.push( start );
    while ( !q.empty() ) {

        start = q.front();      // luam primul nod din coada
        answer = vec[start];
        q.pop();                // stergem nodul din coada

        for ( int i = 0; i < v[start].size(); i ++ ) { // parcurgem vecinii nodului
            if ( !vec[v[start][i]] ) {              // daca nu a mai fost vizitat
                vec[v[start][i]] = vec[start] + 1;  // upddate distanta
                q.push( v[start][i] );              // punem nodul in coada
            }
        }
    }

    d_max = start;      // distanta maxima
}

int main()
{
    f >> n;
    for ( int i = 0; i < n - 1; ++ i ) {
        int a, b; f >> a >> b;
        v[a].push_back( b );    // retinem
        v[b].push_back( a );    //      graful
    }

    memset ( vec, 0, sizeof( vec ) );
    distanta( n );         // ne ducem intr o  exremitate a diametrului
    memset ( vec, 0, sizeof( vec ) );
    distanta( d_max );     // aflam diametrul

    g << answer;            // afisare

    return 0;
}