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

【ETOJ P1021】树的遍历 题解(有向图+深度优先搜索+广度优先搜索)

题目描述

给定一棵大小为 n n n,根为 1 1 1 的树,求出其按照 dfsbfs 进行遍历时的顺序。

请将所有出点按照编号从小到大排序后进行遍历。

dfs 为深度优先搜索,bfs 为宽度优先搜索。

输入格式

一个整数 n n n,表示点的个数。 ( 1 ≤ n ≤ 50 ) (1 \leq n \leq 50) (1n50)

接下来一行 n − 1 n-1 n1 个整数,表示点 2 ∼ n 2 \sim n 2n 的父亲 f a i fa_i fai ( 1 ≤ f a i ≤ n ) (1 \leq fa_i \leq n) (1fain)

输出格式

第一行输出 dfs 时的顺序,第二行输出 bfs 时的顺序。

样例输入1

4
1 1 2

样例输出1

1 2 4 3
1 2 3 4

样例输入2

5
1 2 2 4

样例输出2

1 2 3 4 5
1 2 3 4 5

思路

数组 fa 来存储每个节点的父节点,向量数组 edges 来存储图的边。

main 函数中,首先读取节点的数量 n,然后读取每个节点的父节点,将每个节点添加到其父节点的边列表中。接着,对每个节点的边列表进行排序,以保证遍历的顺序。

调用 dfs 函数进行深度优先搜索。在 dfs 函数中,首先将起始节点压入栈 s1,然后在栈不为空的情况下,弹出栈顶元素,打印其值,然后将其所有子节点(除去父节点)压入栈 s2。接着,将 s2 中的所有节点都压入 s1,这样就实现了深度优先的遍历顺序。

调用 bfs 函数进行广度优先搜索。在 bfs 函数中,首先将起始节点加入队列 q1,然后在队列不为空的情况下,弹出队首元素,打印其值,然后将其所有子节点(除去父节点)加入队列。这样就实现了广度优先的遍历顺序。


AC代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e3 + 7;int n;
int fa[N];
vector<int> edges[N];void dfs(int x) {stack<int> s1;stack<int> s2;s1.push(x);while (s1.size()) {int t = s1.top();s1.pop();cout << t << " ";for (auto &i : edges[t]) {if (i == fa[t]) {continue;}s2.push(i);}while (s2.size()) {s1.push(s2.top());s2.pop();}}
}void bfs(int x) {queue<int> q1;q1.push(x);while (q1.size()) {int f = q1.front();q1.pop();cout << f << " ";for (auto &i : edges[f]) {if (i == fa[f]) {continue;}q1.push(i);}}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 2; i <= n; i++) {cin >> fa[i];edges[fa[i]].push_back(i);}for (int i = 1; i <= n; i++) {sort(edges[i].begin(), edges[i].end());}dfs(1);cout << endl;bfs(1);cout << endl;return 0;
}

相关文章:

【ETOJ P1021】树的遍历 题解(有向图+深度优先搜索+广度优先搜索)

题目描述 给定一棵大小为 n n n&#xff0c;根为 1 1 1 的树&#xff0c;求出其按照 dfs 和 bfs 进行遍历时的顺序。 请将所有出点按照编号从小到大排序后进行遍历。 dfs 为深度优先搜索&#xff0c;bfs 为宽度优先搜索。 输入格式 一个整数 n n n&#xff0c;表示点的…...

红队渗透靶机:LEMONSQUEEZY: 1

目录 信息收集 1、arp 2、nmap 3、nikto 4、whatweb 目录扫描 1、dirsearch 2、gobuster WEB phpmyadmin wordpress wpscan 登录wordpress 登录phpmyadmin 命令执行 反弹shell 提权 get user.txt 信息收集 本地提权 信息收集 1、arp ┌──(root㉿ru)-[~…...

【Servlet】——Servlet API 详解

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【Servlet】 本专栏旨在分享学习Servlet的一点学习心得&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 一、HttpServlet二、Htt…...

oracle主库增加redo组数

redo log&#xff08;重做日志&#xff09;&#xff1a; 重做日志&#xff1a;简单来说就是&#xff0c;将oracle数据库的DML、DDL&#xff08;数据库操作语言&#xff0c;数据库定义i语言&#xff09;操作记录在日志中&#xff0c;方便恢复及备库使用&#xff0c;以组的方式管…...

lua只读表

参考《programming in lua》13.4.5中&#xff0c;详细介绍了只读表的用法。建立一个函数&#xff0c;传入一个table&#xff0c;传出一个代理table&#xff0c;其__index指向传入的table&#xff0c;__newIndex直接报error即可&#xff1a; --输入一个table&#xff0c;输出一…...

探索深度学习的边界:使用 TensorFlow 实现高效空洞卷积(Atrous Convolution)的全面指南

空洞卷积&#xff08;Atrous Convolution&#xff09;&#xff0c;在 TensorFlow 中通过 tf.nn.atrous_conv2d 函数实现&#xff0c;是一种强大的工具&#xff0c;用于增强卷积神经网络的功能&#xff0c;特别是在处理图像和视觉识别任务时。这种方法的核心在于它允许网络以更高…...

HarmonyOS案例:摇杆游戏

本案例主要演示如何通过一系列的动画效果以及运算实现摇杆控制组件同步运动的功能&#xff0c;界面简陋无需在意。 欢迎大家的阅读和评价&#xff0c;也欢迎大佬们批评、指正&#xff0c;我将继续努力&#xff0c;奉上更加专业的、高效的代码案例。 import curves from ohos.c…...

Elasticsearch:构建自定义分析器指南

在本博客中&#xff0c;我们将介绍不同的内置字符过滤器、分词器和分词过滤器&#xff0c;以及如何创建适合我们需求的自定义分析器。更多关于分析器的知识&#xff0c;请详细阅读文章&#xff1a; 开始使用 Elasticsearch &#xff08;3&#xff09; Elasticsearch: analyzer…...

Git系列---远程操作

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 引用 1.理解分布式版本控制…...

kafka客户端生产者消费者kafka可视化工具(可生产和消费消息)

点击下载《kafka客户端生产者消费者kafka可视化工具&#xff08;可生产和消费消息&#xff09;》 1. 前言 因在工作中经常有用到kafka做消息的收发&#xff0c;每次调试过程中&#xff0c;经常需要查看接收的消息内容以及人为发送消息&#xff0c;从网上搜寻了一下&#xff0…...

【从0上手Cornerstone3D】如何使用CornerstoneTools中的工具之工具介绍

简单介绍一下在Cornerstone中什么是工具&#xff0c;工具是一个未实例化的类&#xff0c;它至少实现了BaseTool接口。 如果我们想要在我们的代码中使用一个工具&#xff0c;则必须实现以下两个步骤&#xff1a; 使用Cornerstone的顶层addTool函数添加未实例化的工具 将工具添…...

02-Java抽象工厂模式 ( Abstract Factory Pattern )

抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09;是围绕一个超级工厂创建其他工厂 该超级工厂又称为其他工厂的工厂 在抽象工厂模式中&#xff0c;接口是负责创建一个相关对象的工厂&#xff0c;不需要显式指定它们的类 每个生成的工厂都能按照工厂模式提供对象 …...

yarn/npm certificate has expired

目录 报错 原因&#xff1a;HTTPS 证书验证失败 方法 a.检查网络安全软件&#xff1a;可能会拦截或修改 HTTPS 流量 b.strict-ssl:false关闭验证【临时方法】 报错 info No lockfile found. [1/4] Resolving packages... error Error: certificate has expired at TLS…...

第十三篇【传奇开心果系列】Python的OpenCV库技术点案例示例:光流估计

传奇开心果短博文系列 系列短博文目录Python的OpenCV库技术点案例示例:光流估计短博文目录前言一、光流估计介绍二、Lucas-Kanade光流介绍和示例代码三、Horn-Schunck光流介绍和示例代码四、cv::calcOpticalFlowPyrLK()函数实现光流估计介绍和示例代码五、光流估计用于运动分析…...

iOS面试题

iOS面试题 1. 什么是iOS中的Autolayout&#xff1f; Autolayout是iOS开发中用于实现自适应界面布局的技术。它基于约束&#xff08;Constraints&#xff09;来描述视图之间的关系&#xff0c;以便在不同的设备和屏幕尺寸上正确地布局和调整视图。 Autolayout使用一组规则和优…...

【5G SA流程】5G SA下终端完整注册流程介绍

博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客内容主要围绕: 5G/6G协议讲解 …...

101 C++内存高级话题 内存池概念,代码实现和详细分析

零 为什么要用内存池&#xff1f; 从前面的知识我们知道&#xff0c;当new 或者 malloc 的时候&#xff0c;假设您想要malloc 10个字节&#xff0c; char * pchar new char[10]; char *pchar1 malloc(10); 实际上编译器为了 记录和管理这些数据&#xff0c;做了不少事情&…...

算计是一种混合了感性和理性的非纯粹逻辑系统

算计是人类带有动因的感性与理性混合超&#xff08;计&#xff09;算&#xff0c;是还未形成逻辑状态的非逻辑系统。算计是指人类在进行决策、推理、思考等活动时&#xff0c;融合了感性和理性的思维过程。它是一种超越纯粹逻辑思维的综合性思维方式。感性是指个体基于感觉、直…...

Python 处理小样本数据的文档分类问题

在处理小样本数据的文档分类问题时&#xff0c;可以尝试使用迁移学习或者基于预训练模型的方法&#xff0c;如BERT、GPT等。然而&#xff0c;直接在这里编写一个完整的深度学习文档分类代码超出了这个平台的限制&#xff0c;但我可以为你提供一个基本的思路和简单示例&#xff…...

centos7安装oracle

1 安装虚拟机 设置4G内存&#xff0c;硬盘40G 2 配置网络环境 2.1配置主机名 # vi /etc/hostname 修改为 oracle2.2 配置IP地址 # vi /etc/sysconfig/network-scripts/ifcfg-ens33 修改 BOOTPROTO"static" ONBOOT"yes" IPADDR192.168.109.110 NETMAS…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...