当前位置: 首页 > article >正文

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";
}


http://www.kler.cn/a/587301.html

相关文章:

  • HTML+CSS基础(了解水平)
  • 【QT】-一文读懂抽象类
  • golang从入门到做牛马:第二十一篇-Go语言错误处理:优雅的“故障排除”
  • Vuex 高级技巧与最佳实践
  • JavaScript泄露浏览器插件信息引发的安全漏洞及防护措施
  • Vuex 基础概念与环境搭建
  • Unity开发中对象池设计与使用
  • c语言整理
  • 高德地图猎鹰服务调用指南(Java后端)
  • 【统计学相关笔记】抽样基本定理的证明
  • SpringBoot——Maven篇
  • 掌握这些 UI 交互设计原则,提升产品易用性
  • JConsole:JDK性能监控利器之JConsole的使用说明与案例实践
  • Linux 中的管道:进程间数据传输的利器
  • Cursor 终极使用指南:从零开始走向AI编程
  • 平安养老险深圳分公司积极开展2025年“3·15”金融消费者权益保护教育宣传活动
  • 如何在androidstudio开发环境中查看sqlite数据库(按新版本Android Studio Giraffe提供详细步骤和操作说明,附截图,代码)
  • 极简版:阿里云 ECS 搭建 WordPress
  • Cocos Creator Shader入门实战(四):预处理宏定义和Chunk
  • Docker 》》Docker Compose 》》network 网络 compose