Cod sursa(job #1453188)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 22 iunie 2015 22:08:02
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int> ve[100005];
int be[100005];
void dfs(int x)
{
   int i;
   for(i=ve[x].size()-1;i>=0;i--)
   if(be[ve[x][i]]==0)
   {
       be[ve[x][i]]=be[x]+1;
       dfs(ve[x][i]);
   }
}
int main()
{
    freopen("diametru.in","r",stdin);
    freopen("diametru.out","w",stdout);
    int n,i,j,x,y,ma=0;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ve[x].push_back(y);
        ve[y].push_back(x);
    }
    be[1]=1;
    dfs(1);
    for(i=1;i<=n;i++)
    {
    if(be[i]>ma)
    {
        ma=be[i];
        x=i;
    }
    be[i]=0;
    }
    ma=0;
    be[x]=1;
    dfs(x);
    for(i=1;i<=n;i++)
    if(be[i]>ma)
    ma=be[i];
    printf("%d\n",ma);
    return 0;
}