当前位置: 首页 > 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…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

iOS 项目怎么构建稳定性保障机制?一次系统性防错经验分享(含 KeyMob 工具应用)

崩溃、内存飙升、后台任务未释放、页面卡顿、日志丢失——稳定性问题&#xff0c;不一定会立刻崩&#xff0c;但一旦积累&#xff0c;就是“上线后救不回来的代价”。 稳定性保障不是某个工具的功能&#xff0c;而是一套贯穿开发、测试、上线全流程的“观测分析防范”机制。 …...

第2课 SiC MOSFET与 Si IGBT 静态特性对比

2.1 输出特性对比 2.2 转移特性对比 2.1 输出特性对比 器件的输出特性描述了当温度和栅源电压(栅射电压)为某一具体数值时,漏极电流(集电极电流...