PAT甲级(Advanced Level) Practice 1021 Deepest Root

原题

1021 Deepest Root - PAT (Advanced Level) Practice
标题大意

给定一个连通且无环的图（即树），树的高度取决于根节点的选择。请找出能使树的高度最大的全部根节点（称为“最深根”）。若给定的图不是树（即不连通），需输出连通分量的数目。
解题思绪

先找连通分量的数目，利用bfs遍历全部点，标记已经遍历的点，调用函数bfs的次数就是连通分量的个数。
若为树，利用两次bfs和无序聚集unordered_set来生存使树深度最大的点，只用一次bfs有可能遇到如图环境：假设我们从G点开始遍历，M点就不会进入答案，因此我们先遍历一次，找到最远的为B，再从B开始遍历，找到M。

代码(c++)

1. #include <bits/stdc++.h>
2. #include <algorithm>
3. #include <vector>
4. #include <queue>
5. #include <unordered_set>
7. using namespace std;
9. const int N = 10010;
11. int n;
12. vector<vector<int>> graph(N);          // 模拟邻接表
13. vector<bool> visited(N, false);
15. vector<int> bfs(int start, const vector<vector<int>>& graph, int n) {
16.     vector<int> depth(n + 1, -1);      // 记录每个点的深度
17.     queue<int> q;
18.     q.push(start);
19.     depth[start] = 0;
20.     int max_depth = 0;                 // 动态记录最深的深度
21.    
22.     while (!q.empty()) {
23.         int u = q.front();
24.         q.pop();
25.         for (int v : graph[u]) {
26.             if (depth[v] == -1) {
27.                 depth[v] = depth[u] + 1;
28.                 max_depth = max(max_depth, depth[v]);
29.                 q.push(v);
30.             }
31.         }
32.     }
33.    
34.     vector<int> res;
35.     for (int i = 1; i <= n; ++i) {
36.         if (depth[i] == max_depth) {
37.             res.push_back(i);
38.         }
39.     }
40.     return res;
41. }
43. int main() {
44.     cin >> n;
45.     for(int i = 0; i < n - 1; i++) {
46.         int u, v;
47.         cin >> u >> v;
48.         graph[u].push_back(v);
49.         graph[v].push_back(u);
50.     }
52.     int components = 0;
53.     for (int i = 1; i <= n; ++i) {
54.         if (!visited[i]) {
55.             components++;
56.             queue<int> q;
57.             q.push(i);
58.             visited[i] = true;
59.             while (!q.empty()) {
60.                 int u = q.front();
61.                 q.pop();
62.                 for (int v : graph[u]) {
63.                     if (!visited[v]) {
64.                         visited[v] = true;
65.                         q.push(v);
66.                     }
67.                 }
68.             }
69.         }
70.     }
71.     if(components == 1) {
72.         // 两次遍历找到所有最深的点
73.         vector<int> Y = bfs(1, graph, n);               
74.         vector<int> Z = bfs(Y[0], graph, n);
75.    
76.         unordered_set<int> deepest;
77.         for (int y : Y) deepest.insert(y);
78.         for (int z : Z) deepest.insert(z);
79.         vector<int> ans(deepest.begin(), deepest.end());
80.         sort(ans.begin(), ans.end());
81.    
82.         for (int node : ans) {
83.             cout << node << endl;
84.         }
85.     }
86.     else cout << "Error: "<< components << " components";
87. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。