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++)
#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[start] = 0;
int max_depth = 0; // 动态记录最深的深度
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (depth[v] == -1) {
depth[v] = depth[u] + 1;
max_depth = max(max_depth, depth[v]);
q.push(v);
}
}
}
vector<int> res;
for (int i = 1; i <= n; ++i) {
if (depth[i] == 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[u].push_back(v);
graph[v].push_back(u);
}
int components = 0;
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
components++;
queue<int> q;
q.push(i);
visited[i] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
}
if(components == 1) {
// 两次遍历找到所有最深的点
vector<int> Y = bfs(1, graph, n);
vector<int> Z = bfs(Y[0], 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";
}