Cod sursa(job #1240992)

Utilizator ConstantinPetroviciPetrovici Constantin ConstantinPetrovici Data 12 octombrie 2014 14:22:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

const int MAX=1000000;
#define pb push_back

using namespace std;

int n , d[MAX] , dmax ,last ;
queue <int> q;
vector <int> arb[MAX];

void bfs (int x)
{
    memset (d , 0 , MAX ) ;
    q.push(x);
    d[x]=1;
    while (!q.empty())
    {
        int w=q.front();
        q.pop();
        for ( int i = 0 ; i < ( int ) arb[w].size() ; ++i ){
            if ( d[arb[w][i]] == 0 ) {
                                    d[arb[w][i]]=1+d[w];
                                    q.push(arb[w][i]);
                                     }
            if (d[arb[w][i]]>dmax){dmax=d[arb[w][i]];
        last = arb[w][i] ;
            }
        }
    }
}
int main()
{
    freopen ("darb.in" , "r" , stdin ) ;
    freopen ("darb.out" , "w" , stdout ) ;
    scanf ("%d" , &n ) ;
    for ( int i = 1 ; i < n ; ++i )
    {
        int x , y ;
        scanf ("%d%d" , &x , &y ) ;
        arb[x].pb(y);
        arb[y].pb(x);
    }
    bfs(1);
    bfs(last);
    printf ("%d" , dmax );
    return 0;
}