Pagini recente » Cod sursa (job #2172633) | Cod sursa (job #2863729) | Cod sursa (job #1207418) | Cod sursa (job #155657) | Cod sursa (job #1709640)
#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);
}
}