Cod sursa(job #1107090)

Utilizator MKLOLDragos Ristache MKLOL Data 13 februarie 2014 17:09:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>

#define pb push_back

using namespace std;

vector<int> g[101010];
int c[101010];
int maxim=-1,x,y,N,start;
int ret=0;
void df(int x,int cost){
    c[x]=cost;
    for(int i=0;i<g[x].size();++i){
        if(c[g[x][i]] == 0){
            df(g[x][i],cost+1);
        }
    }
}

int main(){
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<N;++i){
        scanf("%d%d",&x,&y);
        g[x].pb(y);
        g[y].pb(x);
    }
    df(1,1);
    for(int i=1;i<=N;++i){
        if(c[i] > maxim){
            maxim=c[i];
            start = i;
        }
        c[i]=0;
    }
    df(start,1);
    for(int i=1;i<=N;++i){
        if(c[i] > ret){
            ret=c[i];

        }
        c[i]=0;
    }
    printf("%d",ret);

    return 0;
}