Cod sursa(job #1620328)

Utilizator felipeGFilipGherman felipeG Data 29 februarie 2016 06:53:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#define Nmax 100005
using namespace std;

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

int p[ Nmax ], n, nrm;
vector < int > v[ Nmax ];

void citire ()
{
    int a, b;

    f >> n;

    while ( f >> a >> b )
    {
        v[ a ].push_back ( b );
        v[ b ].push_back ( a );
    }
}

void DFS ( int cnt, int a )
{
    int b = 0;

    p[ a ] = cnt;
    for ( int i = 0; i < (int)v[ a ].size(); ++ i )
    {
        b = v[ a ][ i ];

        if ( not p[ b ] )
            DFS ( cnt + 1, b );
    }
}

void run ()
{

    DFS ( 1, 1 );

    int maxi = 0, d = 1;
    for (int i = 1; i <= n; ++ i )
    {
        if ( maxi < p[ i ] )
        {
            maxi = p[ i ];
            d = i;
        }
        p[ i ] = 0;
    }

    DFS ( 1, d );
    maxi = 0;

    for ( int i = 1; i <= n; ++ i )
    {
        if ( maxi < p[ i ] )
            maxi = p[ i ];
    }

    g << maxi;
}

int main()
{
    citire ();
    run ();
    return 0;
}