Cod sursa(job #1337677)

Utilizator iarbaCrestez Paul iarba Data 9 februarie 2015 12:46:13
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
using namespace std;
int st[100001],sf[100001],dir[200001],next[200001],stiv[100001],dist[100001],viz[100001];
int n,i,aux,pos,nod,ms,x,y;
void add(int n1, int n2)
{
	pos++;
	if(st[n1]==0){st[n1]=pos;}
	else{next[sf[n1]]=pos;}
	sf[n1]=pos;
	dir[pos]=n2;
	next[pos]=0;
}
void bfs(int i)
{
	nod=stiv[i];
	int j=st[nod];
	while(j){
		if(viz[dir[j]]==0){
			viz[dir[j]]=1;
			stiv[++ms]=dir[j];
			dist[ms]=dist[i]+1;
						  }
		j=next[j];
			}
	if(i<n)	bfs(i+1);
}
int main()
{
	freopen("darb.in","r",stdin);
	freopen("darb.out","w",stdout);
	scanf("%ld",&n);pos=0;
	for(i=1;i<n;i++)
	{
		scanf("%ld%ld",&x,&y);
		add(x,y);
		add(y,x);
	}
	stiv[1]=1;viz[1]=1;ms=1;
	bfs(1);
	aux=stiv[n];
	for(i=1;i<=n;i++)
	{
		stiv[i]=0;
		viz[i]=0;
	}
	dist[1]=1;stiv[1]=aux;viz[aux]=1;ms=1;
	bfs(1);
	printf("%ld",dist[n]);
return 0;
}