本代码在ACwing tle,两个数据未过,PTA上AC了
本题目需要注意的一个点是,题目中是先输入一个N,然后输入N-1
行,并非N行,这时对于N==1
必须特判,对于该种情况,一个节点也是树,所以应该输出cout<<1;
代码:
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e4+10;
int h[N],e[2*N],ne[2*N];
int p[N];
int n;
int idx;
int max_size;
int st[N];
typedef pair<int,int>pii;
bool cmp(pii a,pii b){
if(a.second!=b.second)
return a.second>b.second;
else
return a.first<b.first;
}
int find(int u){
if(u!=p[u])p[u]=find(p[u]);
return p[u];
}
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int root,int depth){
if(!root)
return ;
max_size=max(max_size,depth);
st[root]=1;
for(int i=h[root];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
dfs(j,depth+1);
}
}
}
int main(){
cin>>n;
if(n==1){
cout<<"Error: 1 components"<<endl;
return 0;
}
for(int i=1;i<=n;i++)p[i]=i;
memset(h,-1,sizeof h);
for(int i=1;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
int dl=find(l),dr=find(r);
if(dl!=dr){
p[dl]=dr;
}
add(l,r);
add(r,l);
}
int temp=0;
for(int i=1;i<=n;i++){
if(p[i]==i){
temp++;
}
}
vector<pii>ans;
if(temp!=1){
cout<<"Error: "<<temp<<" components";
}
else{
for(int i=1;i<=n;i++){
memset(st,0,sizeof st);
dfs(i,0);
ans.push_back({i,max_size});
max_size=0;
}
sort(ans.begin(),ans.end(),cmp);
int tt=ans[0].second;
for(int i=0;i<ans.size();i++){
if(ans[i].second==tt){
if(i<ans.size()-1&&ans[i+1].second==tt){
printf("%d\n",ans[i].first);
}
else{
printf("%d",ans[i].first);
}
}
}
}
return 0;
}