Cod sursa(job #1448338)

Utilizator SilviuIIon Silviu SilviuI Data 6 iunie 2015 18:18:55
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <limits.h>
#include <algorithm>
#include <deque>
#define nmax 100010
using namespace std;
int n,x,i,y,d[nmax],dmax=0,maxnod;
vector <int> a,g[nmax];
queue <int> que;
inline void bfs(int x)
{
    int i; que.push(x); maxnod=0; dmax=0;
    memset(d,0,sizeof(d)); d[x]=1;
    while (!que.empty()){
        x=que.front(); a=g[x]; que.pop();
        for (i=0;i<a.size();i++)
            if (d[a[i]]==0){ d[a[i]]=d[x]+1; que.push(a[i]); }
    }
    for (i=1;i<=n;i++)
    if (d[i]>dmax) { dmax=d[i]; maxnod=i; }
}
int main(){
freopen("darb.in","r",stdin);
freopen("darb.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n-1;i++){
    scanf("%d%d",&x,&y);
    g[x].push_back(y);
    g[y].push_back(x);
}
bfs(1);
bfs(maxnod);
printf("%d",dmax);
return 0;
}