Cod sursa(job #1499336)

Utilizator Julian.FMI Caluian Iulian Julian. Data 10 octombrie 2015 15:15:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <stdlib.h>
#include <fstream>
#define nmax 100005

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

long *g[nmax],viz[nmax];

long bfs1(long x)
{long in,sf,q[nmax],y,i;
viz[x]=1;in=sf=0;q[in]=x;
while(in <= sf)
{y=q[in++];
 for(i=1;i<=g[y][0];i++)
    if(!viz[ g[y][i] ])
        {viz[g[y][i]]=1;
        q[++sf]=g[y][i];}}
return y;}

long d[nmax];

long bfs2(long x)
{long in,sf,q[nmax],y,i;
in=sf=0;q[in]=x;d[x]=1;
while(in<=sf)
{y=q[in++];
for(i=1;i<=g[y][0];i++)
    if(!d[g[y][i]])
    {d[g[y][i]]=d[y]+1;
    q[++sf]=g[y][i];}
}
return d[y];
}

int main()
{long i,n,x,y,j;
    fin>>n;
    for(i=1;i<=n;i++)
        {g[i]=(long*)realloc(g[i],sizeof(long));
        g[i][0]=0;}

    for(i=1;i<n;i++)
        {fin>>x>>y;
        g[x][0]++;
        g[x]=(long*)realloc(g[x],(g[x][0]+1)*sizeof(long) );
        g[x][g[x][0]]=y;

        g[y][0]++;
        g[y]=(long*)realloc(g[y],(g[y][0]+1)*sizeof(long) );
        g[y][g[y][0]]=x;}



        fout<<bfs2(bfs1(1));
}