学步园

/*
  1.使用并查集判断图是否为连通的。
  2.任意选取一点（此处取1，如不取1在n=1的情况下错误），做dfs搜索，选取其中最远距离的点集合A，
   再从点集合A取一点做一次dfs，找到的所有距离最远的点以及集合A都是deepest root。
*/
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<cstdlib>
#define mem_size 10005
using namespace std;
vector<int> vlink[mem_size];
set<int>ans;
set<int>::iterator it;
int father[mem_size],size[mem_size],vst[mem_size];
int n,root,maxn;
int find(int x){
  if(father[x]==x) return x;
  else return father[x]=find(father[x]); 
}
void Union(int a,int b){
  int fa=find(a);
  int fb=find(b);
  if(fa!=fb){
    if(size[fa]<=size[fb]){
      father[fa]=fb;
      size[fb]+=size[fa];
    }
    else{
      father[fb]=fa;
      size[fa]+=size[fb];
    }
  }
}
void init(){
  int i;
  for(i=1;i<=n;i++){
    size[i]=0;
    vst[i]=0;
    father[i]=i;
  }
}

void dfs(int p,int step){
  int i;
  if(step>maxn){
    maxn=step;
    ans.clear();
    ans.insert(p);
  }
  else if(step==maxn){
    ans.insert(p);
  }
  for(i=0;i<vlink[p].size();i++){
    if(vst[vlink[p][i]]==0){
      vst[vlink[p][i]]=1;
      dfs(vlink[p][i],step+1);
      vst[vlink[p][i]]=0;
    }
  }
}

int main(){
  int i,j,fr,to;
  cin>>n;
  init();
  for(i=1;i<n;i++){
    cin>>fr>>to;
    vlink[fr].push_back(to);
    vlink[to].push_back(fr);
    Union(fr,to);
  }
  int cnt=0; 
  for(i=1;i<=n;i++){
    if(father[i]==i){
      cnt++;
    }
  }
  if(cnt>1){
    cout<<"Error: "<<cnt<<" components"<<endl;  
  }
  else{
      maxn=-1; 
      vst[1]=1;
      dfs(1,1);
      vst[1]=0;
     
     set<int> anstmp;
     for(it=ans.begin();it!=ans.end();it++){
         anstmp.insert(*it);
     }
     int one=*(ans.begin());
     maxn=-1; 
     vst[one]=1;
     dfs(one,1);
     vst[one]=0;
        
     for(it=anstmp.begin();it!=anstmp.end();it++){
         ans.insert(*it);
     }  
     
    for(it=ans.begin();it!=ans.end();it++){
      cout<<*it<<endl;
    }
  }
  system("pause");
  return 0;
}