Cod sursa(job #1953334)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 4 aprilie 2017 19:25:24
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> vec[100002];
int ss[100002];
int mx;
void bfs(int x,int c)
{
    ss[x]=c;
    int i,l=vec[x].size();
    for(i=0;i<l;i++)
        if(ss[vec[x][i]]==0)
            {c++;bfs(vec[x][i],c);c--;}
}
int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    int n,i,x,y;
    scanf("%d",&n);
    n--;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    bfs(1,1);
    int cap1;
    mx=-1;
    for(i=1;i<=n;i++)
        {if(ss[i]>mx)
            mx=ss[i],cap1=i;
            ss[i]=0;}
    bfs(cap1,1);
    mx=-1;
    for(i=1;i<=n;i++)
        if(ss[i]>mx)
            mx=ss[i];
    mx++;
    printf("%d",mx);
    return 0;
}