Cod sursa(job #1105786)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 12 februarie 2014 08:56:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
#include <queue>
#define nmax 100005
using namespace std;

vector <int> v[nmax];
queue <int> q;
int l[nmax],mx,mxp;
int d[nmax],dmax;
int n;

int bfs(int start) {
	d[start] = 1;
	q.push(start);
	while (!q.empty()) {
		int n = q.front();q.pop();
		for (vector <int> :: iterator it = v[n].begin();it != v[n].end();it++) {
				if (d[*it] != 0) continue;
				d[*it] = d[n]+1;
				if (d[*it] > dmax) dmax = d[*it];
				q.push(*it);
		}
	}
	return dmax;
}

int main() {
	freopen("darb.in","r",stdin);
	freopen("darb.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
		if (a>b) int aux = a,a=b,b=aux;
		l[b] = l[a]+1;
		if (l[b] > mx) mx=l[b],mxp=b;
	}
	printf("%d\n",bfs(mxp));
	return 0;
}