Cod sursa(job #1093901)

Utilizator pulseOvidiu Giorgi pulse Data 28 ianuarie 2014 19:01:28
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define NMAX 1000003

int n, diametru, last;
int count[NMAX];
bool used[NMAX];
vector <int> v[NMAX];
queue <int> q;

void ReadData ()
{
	scanf ("%d", &n);
	for (int i = 1, a, b; i <= n; ++i)
	{
		scanf ("%d %d", &a, &b);
		v[a].push_back (b);
		v[b].push_back (a);
	}
}

void BFS (int start)
{
	q.push (start);
	used[start] = true;
	count[start] = 1;
	while (!q.empty ())
	{
		int k = q.front ();
		q.pop ();
		for (int i = 0; i < v[k].size (); ++i)
		{
			if (!used[v[k][i]])
			{
				used[v[k][i]] = true;
				q.push (v[k][i]);
				count[v[k][i]] = count[k] + 1;
				diametru = count[v[k][i]];
				last = v[k][i];
			}
		}
	}
}

int main ()
{
	freopen ("darb.in", "r", stdin);
	freopen ("darb.out", "w", stdout);
	ReadData ();
	BFS (1);
	memset (count, 0, sizeof(count));
	memset (used, false, sizeof(used));
	BFS (last);
	printf ("%d", diametru);
	return 0;
}