Cod sursa(job #1104831)

Utilizator classiusCobuz Andrei classius Data 11 februarie 2014 08:16:28
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
using namespace std;

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>

const int MAXN=100100;
vector<int> v[MAXN];
int ds[MAXN];

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

    int n;
    scanf("%d",&n);

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

    ds[1]=1;
    queue<int> q;
    q.push(1);

    while(!q.empty()){
        int i=q.front();
        q.pop();

        for(unsigned j=0;j<v[i].size();j++){
            int u=v[i][j];
            if(!ds[u]){
                ds[u]=ds[i]+1;
                q.push(u);
            }
        }
    }

    int start=max_element(ds+1,ds+n+1)-ds;
    memset(ds,0,sizeof(ds));
    q.push(start);
    ds[start]=1;

    while(!q.empty()){
        int i=q.front();
        q.pop();

        for(unsigned j=0;j<v[i].size();j++){
            int u=v[i][j];
            if(!ds[u]){
                ds[u]=ds[i]+1;
                q.push(u);
            }
        }
    }

    printf("%d",*max_element(ds+1,ds+n+1));

    return 0;
}