Cod sursa(job #1380170)

Utilizator misu007Pogonaru Mihai misu007 Data 6 martie 2015 22:36:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <queue>
using namespace std;

int n,dist[100001];

struct nod
{
    int x;
    nod* u;
}*a[100001];

void adauga(int x,int y)
{
    nod *nd=new nod;
    nd->u=a[x];
    nd->x=y;
    a[x]=nd;
}

int bfs(int x)
{
    int i;
    queue <int> q;
    nod *nd;
    for(i=1;i<=n;++i) dist[i]=-1;
    q.push(x);
    dist[x]=1;
    while(!q.empty())
    {
        i=q.front();
        nd=a[i];
        while(nd)
        {
            if(dist[nd->x]==-1)
            {
                dist[nd->x]=dist[i]+1;
                q.push(nd->x);
            }
            nd=nd->u;
        }
        q.pop();
    }
    return i;
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    int m,x,y;
    scanf("%d",&n);
    m=n-1;
    while(m)
    {
        --m;
        scanf("%d%d",&x,&y);
        adauga(x,y);adauga(y,x);
    }
    x=bfs(1);
    y=bfs(x);
    printf("%d\n",dist[y]);
    return 0;
}