Cod sursa(job #1196856)

Utilizator ion824Ion Ureche ion824 Data 9 iunie 2014 13:45:36
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<cstring>
using namespace std;
typedef struct lnod {
	int vf;
	lnod *next;
}*Nod;

Nod a[100005];
int d[100005], Q[100005];

void add(Nod &q, int y){
	Nod p = new lnod;
	p->vf = y;
	p->next = q;
	q = p;
}

void BFS(int sursa){
	int vf = 1, i, nod;
	
	memset(d,-1,sizeof(d));
	d[sursa] = 0;
	Q[1] = sursa;
	
	for(i=1;i<=vf;++i)
	{
		nod = Q[i];
		for(Nod p = a[nod];p;p=p->next)
		if(d[p->vf] == -1)
		{
			d[p->vf] = d[nod] + 1;
			Q[++vf] = p->vf;
		}
	}	
}

int main(){
	ifstream cin("darb.in");
	ofstream cout("darb.out");
	int N,i,x,y;
	
	cin>>N;
	for(i=1;i<N;++i)
	{
		cin>>x>>y;
		add(a[x],y);
		add(a[y],x);
	}
	
	BFS(1);
	int dmax=0;
	for(i=1;i<=N;++i)
	  if(d[i] > d[dmax]) dmax = i;
	
	BFS(dmax);
	dmax = 0;
	for(i=1;i<=N;++i)
	  if(d[i] > dmax) dmax = d[i];
	
	cout << dmax + 1 << '\n';
	
	return 0;
}