题目链接：https://www.patest.cn/contests/pat-a-practise/1021
题意：无环连通图也可以视为一棵树，选定图中任意一点作为根，如果这时候整个树的深度最大，该点称为 deepest root。 给定一个图，按升序输出所有 deepest root。如果给定的图有多个连通分量，则输出连通分量的数量。
要想树的深度最大，那么树跟一定是一个度为1的点，所以我们只需要找到这些点，然后每个点搜一遍得到最大高度，然后按条件输出即可。当然开始得先判联通，我是用深搜判的。
看网上其他人的做法，很多是先随便选一个点搜一遍，找出距离最大的点，以这个点再搜一遍，最后得到的距离最大的点加上这个点即是答案。这样做看似有道理，而且能过，但是有的情况是判断不了的，比如下面这组数据：
in:
5 1 2 1 3 2 4 2 5 out: 3 4 5
因此这种算法虽然效率高但还需要改进。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; vector<int> m[10010]; //邻接表存图 int vis[10010]; int deg[10010]; //记录度数 int ans[10010]; int n; void dfs(int x) { //判联通 vis[x] = 1; for (int i = 0; i < m[x].size(); i++) { if (!vis[m[x][i]]) dfs(m[x][i]); } } struct node { int id, step; }; int bfs(int x) { //找最远距离 memset(vis, 0, sizeof(vis)); queue<node> q; node now, next; now.id = x, now.step = 0; q.push(now); vis[x] = 1; int maxl = 0; while(!q.empty()) { now = q.front(); if(now.step > maxl) maxl = now.step; q.pop(); for(int i = 0; i < m[now.id].size(); i++) { if(!vis[m[now.id][i]]) { vis[m[now.id][i]] = 1; next.id = m[now.id][i], next.step = now.step+1; q.push(next); } } } return maxl; } int main() { cin >> n; int x, y; for(int i = 0; i < n - 1; i++) { cin >> x >> y; deg[x]++; deg[y]++; m[x].push_back(y); m[y].push_back(x); } int cnt = 0; for (int i = 1; i <= n; i++) { if (!vis[i]) { cnt++; dfs(i); } } if(cnt == 1) { //联通分量个数为1 int maxn = 0; for(int i = 1; i <= n; i++) { if(deg[i] == 1) { ans[i] = bfs(i); if(ans[i] > maxn) maxn = ans[i]; } } for(int i = 1; i <= n; i++) { if(ans[i] == maxn) cout << i << endl; } } else cout << "Error: " << cnt << " components" << endl; return 0; }
