1021.png

1021-2.png

分析

这道题一开始想要用一个dfs解决，但是好像没办法做到，就再用了并查集统计图的个数。
写的时候又犯了很多粗心的小错误，还是做得太少了！

ac代码

#include<bits/stdc++.h>
using namespace std;

int temp_max;
vector<int> v[10001];
int depth[10001];
int visit[10001];


//дһ¸ö²¢²é¼¯ 
int f[10001];

int find(int a){
    if(f[a]==a){
        return a;
    }else{
        f[a]=find(f[a]);
        return f[a];
    }
} 

void merge(int a,int b){
    int x=find(a);
    int y=find(b);
    if(x!=y){
        f[y]=x;
    }
}



void dfs(int n,int temp){
    if(temp_max<temp){
        temp_max=temp;
    }
    visit[n]=1;
    for(int i=0;i<v[n].size();i++){
        if(visit[v[n][i]]==0){
            visit[v[n][i]]=1;
            dfs(v[n][i],temp+1);
        }
    }
}

int main(){
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        merge(a,b);
    }

    set<int> s;
    for(int i=1;i<=n;i++){
        s.insert(find(i));
    }
    if(s.size()>1){
        printf("Error: %d components",s.size());
        return 0;
    }


    int max=1;
    for(int i=1;i<=n;i++){
        
        for(int j=1;j<=n;j++){
            visit[j]=0;
        }

        temp_max=1;
        dfs(i,1);
        depth[i]=temp_max;
        
        if(temp_max>max){
            max=temp_max;
        }
        
    }
    
    for(int i=1;i<=n;i++){
        if(depth[i]==max){
            cout<<i<<endl;
        }
    }
    
}