测试点1测试的是 整个图只有一个点的时候
#include<cstdio>
#include<set>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10010;
bool vis[maxn];
int father[maxn];
vector<int> graph[maxn];
set<int> ans_A, temp_point;
int find_father(int a) {
if (a == father[a]) return a;
return father[a] = find_father(father[a]);
}
void Unite(int a, int b) {
int fa_a = find_father(a);
int fa_b = find_father(b);
if (fa_a != fa_b)
father[fa_a] = fa_b;
}
int max_height;
void DFS(int u, int height, int pre) {//对算法笔记进行优化,算法笔记上,只要树高大于他,那么就要开始加入vector,但是那么做会损耗很多时间
if ((graph[u].size() == 1 && graph[u][0] == pre) ||graph[u].size() == 0) {//因为每个点都有回去的点,所以当他等于1的时候,那么就代表着没有点了
if (height > max_height) {
temp_point.clear();
temp_point.insert(u);
max_height = height;
}
else if (height == max_height)temp_point.insert(u);
}
else {
for (int i = 0; i < graph[u].size(); i++)
if (graph[u][i] != pre) DFS(graph[u][i], height + 1, u);
}
}
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) father[i] = i;
for (int i = 1; i < n; i++) {
int a, b; scanf("%d %d", &a, &b);
graph[a].push_back(b), graph[b].push_back(a);
Unite(a, b);
}
int block = 0;
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i++) {
int fa = find_father(i);
if (!vis[fa]) {
block++;
vis[fa] = true;
}
}
set<int>::iterator it;
if (block != 1) printf("Error: %d components\n", block);
else {
DFS(1, 1, -1);
ans_A = temp_point;
temp_point.clear();
max_height = 0;
it = ans_A.begin();
DFS(*it, 1, -1);
ans_A.insert( temp_point.begin(), temp_point.end());
}
for (it = ans_A.begin(); it != ans_A.end(); it++)printf("%d\n", *it);
}