Cod sursa(job #1220392)

Utilizator pulseOvidiu Giorgi pulse Data 17 august 2014 11:19:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 100005;
int N, last, Count[MAXN], ans;
vector <int> G[MAXN];
queue <int> Q;
bool Used[MAXN];

void BFS(int v)
{
	Q.push(v);
	Used[v] = 1;
	Count[v] = 1;
	while (!Q.empty())
	{
		int node = Q.front(); Q.pop();
		for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
		{
			if (!Used[*it])
			{
				Used[*it] = 1;
				Q.push(*it);
				Count[*it] = Count[node] + 1;
				ans = Count[*it];
				last = *it;
			}
		}
	}
}

int main()
{
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);
	scanf("%d\n", &N);
	for (int i = 1; i < N; ++i)
	{
		int a, b;
		scanf("%d %d\n", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	BFS(1);
	memset(Used, 0, sizeof(Used));
	memset(Count, 0, sizeof(Count));
	BFS(last);
	printf("%d\n", ans);
	return 0;
}