Cod sursa(job #1709791)

Utilizator Furia_PolitehniciiUPT Statescu Stana Mihut Furia_Politehnicii Data 28 mai 2016 13:53:26
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.59 kb
#include <stdio.h>
#include <vector>

using namespace std;

const int dim = 100005;

int T, N;
vector<int> v[dim];
int viz[dim];
int running, longest_dist, initial_longest_dist;
int extreme_node, prev_extreme_node, new_extreme_node;

void dfs(int n, int dist) {

	if (dist > longest_dist) {
		longest_dist = dist;
		new_extreme_node = n;
	}

	viz[n] = 1;

	for (int i = 0; i < v[n].size(); i++) {
		int vecin = v[n][i];
		if (viz[vecin] == 0) {
			dfs(vecin, dist + 1);
		}
	}
}

void find_extremes(int node_start, int ignored_node) {
	extreme_node = node_start;
	prev_extreme_node = -1;
	new_extreme_node = -1;

	while (1) {

		longest_dist = 0;
		for (int i = 0; i < N; i++) {
			viz[i] = 0;
		}
		viz[ignored_node] = 1;

		dfs(extreme_node, 0);
		//printf("%d -> %d\n", extreme_node, new_extreme_node);

		if (prev_extreme_node == new_extreme_node) {
			break;
		}
		
		prev_extreme_node = extreme_node;
		extreme_node = new_extreme_node;
	}

	//printf("\n");
}

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

	scanf("%d", &T);

	while(T--) {

		scanf("%d", &N);

		for (int i = 0; i < N; i++) {
			v[i].clear();
			viz[i] = 0;
		}

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

		find_extremes(0, -1);

		initial_longest_dist = longest_dist;
		int node1 = new_extreme_node;
		int node2 = extreme_node;
		
		find_extremes(node2, node1);

		if (initial_longest_dist > longest_dist) {
			printf("%d\n", longest_dist);
			continue;
		}

		find_extremes(node1, node2);

		printf("%d\n", longest_dist);
	}

	return 0;
}