Cod sursa(job #1320343)

Utilizator atatomirTatomir Alex atatomir Data 17 ianuarie 2015 21:02:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define maxN 100011

long n,i,x,y,best,bestI;
vector<long> list[maxN];
long dp[maxN];
queue<long> Q;

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);

    scanf("%ld",&n);
    for(i=1;i<n;i++){
        scanf("%ld %ld",&x,&y);
        list[x].push_back(y);
        list[y].push_back(x);
    }

    dp[1]=1; Q.push(1); best=0;
    while(!Q.empty()){
        long nod = Q.front(); Q.pop();
        if(dp[nod] > best){
            best = dp[nod];
            bestI = nod;
        }
        for(long i=0;i<list[nod].size();i++){
            long newNode = list[nod][i];
            if(!dp[newNode]) {
                dp[newNode] = dp[nod]+1;
                Q.push(newNode);
            }
        }
    }

    memset(dp,0,sizeof(dp));
    dp[bestI]=1; Q.push(bestI); best=0;
    while(!Q.empty()){
        long nod = Q.front(); Q.pop();
        if(dp[nod] > best){
            best = dp[nod];
            bestI = nod;
        }
        for(long i=0;i<list[nod].size();i++){
            long newNode = list[nod][i];
            if(!dp[newNode]) {
                dp[newNode] = dp[nod]+1;
                Q.push(newNode);
            }
        }
    }

    printf("%ld",best);

    return 0;
}