深度最大的树一定是某个叶子结点做根,可以只遍历叶子结点
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 20010;
int e[M], ne[M], h[N], idx; //邻接表
int p[N], cnt; //并查集
int depth[N], deepest, di; //存输出答案
int d[N]; //结点入度
int n;
void add(int a, int b){
e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
int find(int x){
if( p[x]!=x ) p[x]=find(p[x]);
return p[x];
}
void merge(int a, int b){
a = find(a), b = find(b);
if( a!=b ){
p[a] = b;
cnt--;
}
}
int dfs(int u, int fa){
int t = 0;
for( int i=h[u]; ~i; i=ne[i] ){
int j = e[i];
if( j==fa ) continue;
t = max(t, dfs(j, u));
}
return t + 1;
}
int main(){
memset(h, -1, sizeof h);
int a, b;
scanf("%d", &n);
cnt = n;
for( int i=1; i<=n; i++ ) p[i]=i;
for( int i=1; i<n; i++ ){
scanf("%d %d", &a, &b);
add(a, b), add(b, a); //无向图
merge(a, b);
d[a]++, d[b]++;
}
if( cnt!=1 ) printf("Error: %d components\n", cnt); //不止一个连通分量
else{
for( int i=1; i<=n; i++ ){
if( d[i]==1 || d[i]==0 ){ //叶结点 或 整棵树只有一个结点,没有边
int t = dfs(i, -1);
if( t > deepest ){
deepest = t;
di = 0;
depth[di++] = i;
}
else if( t==deepest ){
depth[di++] = i;
}
}
}
for( int i=0; i<di; i++ ){
printf("%d\n", depth[i]);
}
}
return 0;
}