Cod sursa(job #1394101)

Utilizator DysKodeTurturica Razvan DysKode Data 20 martie 2015 00:00:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int DIM = 100010;

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

vector <int> Adj[DIM];
queue <int> Q;
int i,j,n,m,Freq[DIM],curSiz,curAsc,curPoz,ans,x,y;

void _DFS(int nod, int dist)
{
    int curSiz,curAsc,i;
    if(dist > ans)
        ans = dist;
    curSiz = Adj[ nod ].size();
    for(i=0 ; i<curSiz ; ++i)
    {
        curAsc = Adj[ nod ][ i ];
        if( Freq[ curAsc ] == 1 )
        {
            Freq[ curAsc ] = 2;
            _DFS( curAsc , dist + 1 );
        }
    }
}

int main()
{
    in>>n;
    for(i=1 ; i<n ; ++i)
    {
        in>>x>>y;
        Adj[ x ].push_back( y );
        Adj[ y ].push_back( x );
    }

    Q.push(1);
    Freq[ 1 ] = 1;
    while( !Q.empty() )
    {
        curPoz = Q.front();
        curSiz = Adj[ curPoz ].size();
        for(i=0 ; i<curSiz ; ++i)
        {
            curAsc = Adj[ curPoz ][ i ];
            if( Freq[ curAsc ] == 0 )
            {
                Freq[ curAsc ] = 1;
                Q.push( curAsc );
            }
        }

        Q.pop();
    }
    Freq[ curPoz ] = 2;
    _DFS( curPoz , 1 );

    out<<ans;

return 0;
}