并查集用来判断图是不是树 然后暴力枚举最大深度
注意:因为是无向图e[M] ne[M] 这里卡了一下。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2*N;
int h[N],e[M],ne[M],idx;
int p[N];
int n;
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
int dfs(int x,int father){
int depth=1;
for(int i=h[x];i!=-1;i=ne[i]){
if(e[i]!=father)depth=max(depth,dfs(e[i],x)+1);
}
return depth;
}
int main(){
memset(h,-1,sizeof h);
cin>>n;
for(int i=1;i<=n;i++)p[i]=i;
int cnt=n;//连通块数量
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
if(find(a)!=find(b)){
p[find(a)]=find(b);
cnt--;
}
add(a,b),add(b,a);
}
if(cnt>1)printf("Error: %d components",cnt);//不是树
else{
//暴力枚举
vector<int> ans;
int max_depth=-1;
for(int i=1;i<=n;i++){
int depth=dfs(i,-1);//-1表示没有father
if(depth>max_depth){
max_depth=depth;
ans.clear();
ans.push_back(i);
}else if(depth==max_depth){
ans.push_back(i);
}
}
for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl;
}
}