Cod sursa(job #1302259)

Utilizator whoasdas dasdas who Data 26 decembrie 2014 19:30:18
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#define IA_PROB "darb"

#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <algorithm>

using namespace std;

int n;
vector< vector<int> > tree;
vector<bool> viz;
int lsep = -1;

void bfs(int s, int &last, int &depth)
{
	queue<int> q;

	depth = 0;

	q.push(s);
	q.push(lsep);

	while (true) {
		int c = q.front();
		q.pop();
		if (c == lsep) {
			depth++;
			if (!q.empty()) {
				q.push(lsep);
				continue;
			} else {
				break;
			}
		}
		last = c;
		viz[last] = true;
		for (vector<int>::iterator it = tree[last].begin(); it != tree[last].end(); ++it)
			if (!viz[*it])
				q.push(*it);
	}
}

int main()
{
	freopen(IA_PROB".in", "r", stdin);
	freopen(IA_PROB".out", "w", stdout);

	scanf("%d", &n);
	tree.resize(n);
	viz.resize(n);

	for (int i = 0; i < n - 1; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--; y--;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}

	int last, depth;

	bfs(0, last, depth);
	viz.clear();
	viz.resize(n);
	bfs(last, last, depth);

	printf("%d", depth);

	return 0;
}