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。
https://i-blog.csdnimg.cn/direct/3306e9241df147f58d06a1286ea7cadd.webp
代码(c++)
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
const int N = 10010;
int n;
vector<vector<int>> graph(N); // 模拟邻接表
vector<bool> visited(N, false);
vector<int> bfs(int start, const vector<vector<int>>& graph, int n) {
vector<int> depth(n + 1, -1); // 记录每个点的深度
queue<int> q;
q.push(start);
depth = 0;
int max_depth = 0; // 动态记录最深的深度
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph) {
if (depth == -1) {
depth = depth + 1;
max_depth = max(max_depth, depth);
q.push(v);
}
}
}
vector<int> res;
for (int i = 1; i <= n; ++i) {
if (depth == max_depth) {
res.push_back(i);
}
}
return res;
}
int main() {
cin >> n;
for(int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
graph.push_back(v);
graph.push_back(u);
}
int components = 0;
for (int i = 1; i <= n; ++i) {
if (!visited) {
components++;
queue<int> q;
q.push(i);
visited = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph) {
if (!visited) {
visited = true;
q.push(v);
}
}
}
}
}
if(components == 1) {
// 两次遍历找到所有最深的点
vector<int> Y = bfs(1, graph, n);
vector<int> Z = bfs(Y, graph, n);
unordered_set<int> deepest;
for (int y : Y) deepest.insert(y);
for (int z : Z) deepest.insert(z);
vector<int> ans(deepest.begin(), deepest.end());
sort(ans.begin(), ans.end());
for (int node : ans) {
cout << node << endl;
}
}
else cout << "Error: "<< components << " components";
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]