Cod sursa(job #1684038)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 10 aprilie 2016 18:59:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
using namespace std;

#ifdef INFOARENA
#define ProblemName "darb"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

vector< vector<int> > G;
vector<int> dist;
queue<int> Q;

int bfs(int nod) {
	memset(&dist[0], 0xFF, sizeof(dist[0]) * dist.size());
	while (!Q.empty()) Q.pop();
	Q.push(nod); dist[nod] = 0;
	int mdist = 0, mnod = nod;
	while (!Q.empty()) {
		int t = Q.front();
		Q.pop();
		for (vector<int>::iterator i = G[t].begin(), end = G[t].end(); i != end; ++i)
		if (dist[*i] == -1) {
			dist[*i] = dist[t] + 1;
			if (dist[*i] > mdist) {
				mdist = dist[*i];
				mnod = *i;
			}
			Q.push(*i);
		}
	}
	return mnod;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	int N;
	scanf("%d", &N);
	G.resize(N);
	dist.resize(N);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int u = bfs(0);
	int v = bfs(u);
	printf("%d\n", dist[v] + 1);
	return 0;
}