【ETOJ P1021】树的遍历 题解(有向图+深度优先搜索+广度优先搜索)
题目描述
给定一棵大小为 n n n,根为 1 1 1 的树,求出其按照 dfs 和 bfs 进行遍历时的顺序。
请将所有出点按照编号从小到大排序后进行遍历。
dfs 为深度优先搜索,bfs 为宽度优先搜索。
输入格式
一个整数 n n n,表示点的个数。 ( 1 ≤ n ≤ 50 ) (1 \leq n \leq 50) (1≤n≤50)
接下来一行 n − 1 n-1 n−1 个整数,表示点 2 ∼ n 2 \sim n 2∼n 的父亲 f a i fa_i fai。 ( 1 ≤ f a i ≤ n ) (1 \leq fa_i \leq n) (1≤fai≤n)
输出格式
第一行输出 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,根为 1 1 1 的树,求出其按照 dfs 和 bfs 进行遍历时的顺序。 请将所有出点按照编号从小到大排序后进行遍历。 dfs 为深度优先搜索,bfs 为宽度优先搜索。 输入格式 一个整数 n n n,表示点的…...
红队渗透靶机: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 详解
个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【Servlet】 本专栏旨在分享学习Servlet的一点学习心得,欢迎大家在评论区交流讨论💌 目录 一、HttpServlet二、Htt…...
oracle主库增加redo组数
redo log(重做日志): 重做日志:简单来说就是,将oracle数据库的DML、DDL(数据库操作语言,数据库定义i语言)操作记录在日志中,方便恢复及备库使用,以组的方式管…...
lua只读表
参考《programming in lua》13.4.5中,详细介绍了只读表的用法。建立一个函数,传入一个table,传出一个代理table,其__index指向传入的table,__newIndex直接报error即可: --输入一个table,输出一…...
探索深度学习的边界:使用 TensorFlow 实现高效空洞卷积(Atrous Convolution)的全面指南
空洞卷积(Atrous Convolution),在 TensorFlow 中通过 tf.nn.atrous_conv2d 函数实现,是一种强大的工具,用于增强卷积神经网络的功能,特别是在处理图像和视觉识别任务时。这种方法的核心在于它允许网络以更高…...
HarmonyOS案例:摇杆游戏
本案例主要演示如何通过一系列的动画效果以及运算实现摇杆控制组件同步运动的功能,界面简陋无需在意。 欢迎大家的阅读和评价,也欢迎大佬们批评、指正,我将继续努力,奉上更加专业的、高效的代码案例。 import curves from ohos.c…...
Elasticsearch:构建自定义分析器指南
在本博客中,我们将介绍不同的内置字符过滤器、分词器和分词过滤器,以及如何创建适合我们需求的自定义分析器。更多关于分析器的知识,请详细阅读文章: 开始使用 Elasticsearch (3) Elasticsearch: analyzer…...
Git系列---远程操作
📙 作者简介 :RO-BERRY 📗 学习方向:致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 📒 日后方向 : 偏向于CPP开发以及大数据方向,欢迎各位关注,谢谢各位的支持 引用 1.理解分布式版本控制…...
kafka客户端生产者消费者kafka可视化工具(可生产和消费消息)
点击下载《kafka客户端生产者消费者kafka可视化工具(可生产和消费消息)》 1. 前言 因在工作中经常有用到kafka做消息的收发,每次调试过程中,经常需要查看接收的消息内容以及人为发送消息,从网上搜寻了一下࿰…...
【从0上手Cornerstone3D】如何使用CornerstoneTools中的工具之工具介绍
简单介绍一下在Cornerstone中什么是工具,工具是一个未实例化的类,它至少实现了BaseTool接口。 如果我们想要在我们的代码中使用一个工具,则必须实现以下两个步骤: 使用Cornerstone的顶层addTool函数添加未实例化的工具 将工具添…...
02-Java抽象工厂模式 ( Abstract Factory Pattern )
抽象工厂模式(Abstract Factory Pattern)是围绕一个超级工厂创建其他工厂 该超级工厂又称为其他工厂的工厂 在抽象工厂模式中,接口是负责创建一个相关对象的工厂,不需要显式指定它们的类 每个生成的工厂都能按照工厂模式提供对象 …...
yarn/npm certificate has expired
目录 报错 原因:HTTPS 证书验证失败 方法 a.检查网络安全软件:可能会拦截或修改 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? Autolayout是iOS开发中用于实现自适应界面布局的技术。它基于约束(Constraints)来描述视图之间的关系,以便在不同的设备和屏幕尺寸上正确地布局和调整视图。 Autolayout使用一组规则和优…...
【5G SA流程】5G SA下终端完整注册流程介绍
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客内容主要围绕: 5G/6G协议讲解 …...
101 C++内存高级话题 内存池概念,代码实现和详细分析
零 为什么要用内存池? 从前面的知识我们知道,当new 或者 malloc 的时候,假设您想要malloc 10个字节, char * pchar new char[10]; char *pchar1 malloc(10); 实际上编译器为了 记录和管理这些数据,做了不少事情&…...
算计是一种混合了感性和理性的非纯粹逻辑系统
算计是人类带有动因的感性与理性混合超(计)算,是还未形成逻辑状态的非逻辑系统。算计是指人类在进行决策、推理、思考等活动时,融合了感性和理性的思维过程。它是一种超越纯粹逻辑思维的综合性思维方式。感性是指个体基于感觉、直…...
Python 处理小样本数据的文档分类问题
在处理小样本数据的文档分类问题时,可以尝试使用迁移学习或者基于预训练模型的方法,如BERT、GPT等。然而,直接在这里编写一个完整的深度学习文档分类代码超出了这个平台的限制,但我可以为你提供一个基本的思路和简单示例ÿ…...
centos7安装oracle
1 安装虚拟机 设置4G内存,硬盘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…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
