题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805482919673856
参考：https://www.liuchuo.net/archives/2348

思路

  1. 先判断有几个连通图
  2. 有两个及以上：输出连通量
  3. 只有一个：先从一个结点dfs后保留最高高度拥有的结点们，然后从这些结点中的其中任意一个开始dfs得到最高高度的结点们，这两个结点集合的并集就是所求
  4. 第三点结论好像有证明，我试过把第二个集合去了，只有两个测试点没过

代码

  1. #include<vector>
  2. #include<algorithm>
  3. #include<set>
  4. #include<cstdio>
  5. #include<iostream>
  6. using namespace std;
  7. const int maxn = 10010;
  8. vector<int> G[maxn], temp;
  9. bool vis[maxn];
  10. set<int> s;
  11. int maxheight = 0;
  12. void dfs(int v, int height){
  13.     if(height > maxheight){
  14.         temp.clear();
  15.         temp.push_back(v);
  16.         maxheight = height;
  17.     } else if(height == maxheight){
  18.         temp.push_back(v);
  19.     }
  20.     vis[v] = true;
  21.     for(int i = 0; i < G[v].size(); i++){
  22.         if(vis[G[v][i]] == false) dfs(G[v][i], height + 1);
  23.     }
  24. }
  26. int main(){
  27.     int n;
  28.     scanf("%d", &n);
  29.     for(int i = 0; i < n - 1; i++){
  30.         int a, b;
  31.         scanf("%d%d", &a, &b);
  32.         G[a].push_back(b);
  33.         G[b].push_back(a);
  34.     }
  35.     int a, b, cnt = 0, s1 = 0;
  36.     for(int i = 1; i <= n; i++){
  37.         if(vis[i] == false){
  38.             dfs(i, 1);
  39.             //这个时候已经遍历完了，得到最大高度
  40.             if(i == 1){
  41.                 if(temp.size()!=0) s1 = temp[0];
  42.                 for(int j = 0; j < temp.size(); j++){
  43.                     s.insert(temp[j]);
  44.                 }
  45.             }
  46.             cnt++;
  47.         }
  48.     }
  49.     if(cnt >= 2){
  50.         printf("Error: %d components",cnt);
  51.     } else {
  52.         temp.clear();
  53.         maxheight = 0;
  54.         fill(vis, vis + 10010, false);
  55.         dfs(s1, 1);
  56.         for(int i = 0; i < temp.size(); i++){
  57.             s.insert(temp[i]);
  58.         }
  59.         for(auto it = s.begin(); it != s.end(); it++){
  60.             printf("%d\n", *it);
  61.         }
  62.     }
  63.     return 0;
  64. }