题目链接
《算法笔记》上提到这道题用set更方便， 确实如此， 这道题的规则简直就是为set 量身定制的， 如下：
#include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; const int maxV=100010; vector<int> adj[maxV]; int father[maxV]; int isRoot[maxV]={0}; int n; int findFather(int x){ int a=x; while (x!=father[x]){ x=father[x]; } while (a!=father[a]){ int z=a; a=father[a]; father[z]=x; } return x; } void Union(int a, int b){ int faA=findFather(a); int faB=findFather(b); if (faA!=faB){ father[faA]=faB; } } void init(){ for (int i=1; i<=n; i++){ father[i]=i; } } int calBlock(){ int block=0; for (int i=1; i<=n; i++){ int fa=findFather(i); isRoot[fa]=1; } for (int i=1; i<=n; i++){ block+=isRoot[i]; } return block; } int maxH=0; set<int> temp, ans; void DFS(int u, int height, int pre){ if (height>maxH){ maxH=height; temp.clear(); temp.insert(u); }else if (height==maxH){ temp.insert(u); } for (int i=0; i<adj[u].size(); i++){ if (adj[u][i]!=pre){ DFS(adj[u][i],height+1, u); } } } int main(){ scanf("%d",&n); init(); for (int i=0; i<n-1; i++){ int u,v; scanf("%d %d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); Union(u,v); } int block=calBlock(); if (block!=1){ printf("Error: %d components\n",block); }else { DFS(1,1,-1); ans=temp; DFS(*(ans.begin()),1,-1); for (set<int>::iterator it=temp.begin(); it!=temp.end(); it++){ ans.insert(*it); } for (set<int>::iterator it=ans.begin(); it!=ans.end(); it++){ printf("%d\n",*it); } } }