蓝桥杯备赛 | 洛谷做题打卡day5

news/2024/2/24 6:57:04/文章来源:https://blog.csdn.net/m0_73246124/article/details/135577669

蓝桥杯备赛 | 洛谷做题打卡day5

图论起航,一起来看看深(广)度优先吧 ~

文章目录

  • 蓝桥杯备赛 | 洛谷做题打卡day5
    • 图论起航,一起来看看深(广)度优先吧 ~
    • 【深基18.例3】查找文献
      • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 我的一些话

【深基18.例3】查找文献

题目描述

小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小 K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。

假设洛谷博客里面一共有 n ( n ≤ 1 0 5 ) n(n\le10^5) n(n105) 篇文章(编号为 1 到 n n n)以及 m ( m ≤ 1 0 6 ) m(m\le10^6) m(m106) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章,请帮助小 K 设计一种方法,使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图,其中,文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS,并输出遍历结果。如果有很多篇文章可以参阅,请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

m + 1 m+1 m+1 行,第 1 行为 2 个数, n n n m m m,分别表示一共有 n ( n ≤ 1 0 5 ) n(n\le10^5) n(n105) 篇文章(编号为 1 到 n n n)以及 m ( m ≤ 1 0 6 ) m(m\le10^6) m(m106) 条参考文献引用关系。

接下来 m m m 行,每行有两个整数 X , Y X,Y X,Y 表示文章 X 有参考文献 Y。

输出格式

共 2 行。
第一行为 DFS 遍历结果,第二行为 BFS 遍历结果。

样例 #1

样例输入 #1

8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

样例输出 #1

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8

学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是我的代码 ~

#include<iostream>  //头文件不要忘记啦
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
inline int read()//二进制优化的快读 
{int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}return x * f;
}
int n, m;
bool b[100005];//定义b数组防止重复输出 
vector<int > a[100005];//STL大法好 
void dfs(int x, int r)//x表示所在点,r表示剩余未遍历的点 
{b[x] = true;//记录某点已经输出过 if (!r)//如果每个点都遍历过终止递归 {cout << x << ' ';return;}cout << x << ' ';//输出 for (int i = 0; i < a[x].size(); i++)if (!b[a[x][i]]) dfs(a[x][i], r - 1);//查找从x可以到的点,并遍历 
}
void bfs()
{queue<int> q;//还是STL q.push(1); b[1] = true;//把1点放入队列中,并标记1点已经遍历过 while (!q.empty()){int s = q.front(); q.pop();//拿出队列首的那个点 cout << s << ' ';//输出 for (int i = 0; i < a[s].size(); i++) if (b[a[s][i]] == false) q.push(a[s][i]), b[a[s][i]] = true;//把点s所能到达的点遍历,为防止TLE和重复输出,记录已遍历过的点 }
}
int main()
{n = read();//读入 m = read();for (int i = 1; i <= m; i++){int x, y;x = read();//读入y = read();a[x].push_back(y);//建图 表示x可以到y }for (int i = 1; i <= n; i++)//把每条路所通向的点从小到大排列(题目中有要求) sort(a[i].begin(), a[i].end());//快排  dfs(1, n);//进行深搜 从1点开始,进行n次 cout << endl;//换行 for (int i = 1; i <= n; i++) b[i] = false;//初始化 bfs();//进行广搜 return 0;
}

在这里插入图片描述

我的一些话

  • 关于图论:ww图论确实难度要吊打之前的普通题,但人总是要学会跳出之前的泥淖,才能看见更远的星辰。或许这条路不好走,但要加油呀!学会利用新知,自己多试试并尝试积攒一些固定解答方案,大多数人的努力,其实还没有到拼天赋的程度。在一切未知之前,我们能做的便是享受当下并做自己喜欢且认为有意义的事情。
  • 总结来说思路很重要,多想想,多在草稿纸上画画,用测试数据多调试,debug后成功编译并运行出正确结果真的会感到很幸福!
  • 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识,之前的博文我都有写,欢迎大家翻阅自取~
  • 不管什么都要坚持吧,三天打鱼两天晒网无法形成肌肉记忆和做题思维,该思考的时候一定不要懈怠,今天就说这么多啦,欢迎评论留言,一起成长:)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925227.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue知识-04

计算属性computed 注意&#xff1a; 1、计算属性是基于它们的依赖进行缓存的 2、计算属性只有在它的相关依赖发生改变时才会重新求值 3、计算属性就像Python中的property&#xff0c;可以把方法/函数伪装成属性 4、computed: { ... } 5、计算属性必须要有…

MySQl Mybatis

一、MySQL 1.1 概述 1.1.1 MySQL安装 1.1.2 数据模型 1.1.3 SQL简介 1.2 DDL 1.2.1 数据库操作 1.2.2 图形化工具 1.2.3 表结构操作 &#xff08;一&#xff09;创建 &#xff08;二&#xff09;数据类型 &#xff08;1&#xff09;数值类型 age tinyint unsigned——加上…

Kubernetes 集群管理—日志架构

日志架构 应用日志可以让你了解应用内部的运行状况。日志对调试问题和监控集群活动非常有用。 大部分现代化应用都有某种日志记录机制。同样地&#xff0c;容器引擎也被设计成支持日志记录。 针对容器化应用&#xff0c;最简单且最广泛采用的日志记录方式就是写入标准输出和标…

书生·浦语大模型--第三节课笔记--基于 InternLM 和 LangChain 搭建你的知识库

文章目录 大模型开发范式RAGLangChain框架&#xff1a;构建向量数据库构建检索问答链优化建议web 部署 实践部分环境配置 大模型开发范式 LLM的局限性&#xff1a;时效性&#xff08;最新知识&#xff09;、专业能力有限&#xff08;垂直领域&#xff09;、定制化成本高&#…

测试平台出问题?看我20分钟快速定位!

今天遇到一个问题&#xff0c;感觉挺有意思&#xff0c;处理过程也非常有意义&#xff0c;希望能给大家一个借鉴吧。今天一位小姐姐找到了我们大组长&#xff0c;说测试平台添加自动化测试用例失败&#xff0c;之后我们组长把我拉到了一个群里让我去看一下&#xff0c;硬着头皮…

C++面试宝典第19题:最长公共前缀

题目 编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀,返回空字符串""。说明:所有输入只包含小写字母a-z。 示例1: 输入: ["flower", "flow", "flight"]输出: "fl" 示例2: 输入: ["dog",…

如何在Windows 10/11的防火墙中禁止和允许某个应用程序,这里提供详细步骤

想阻止应用程序访问互联网吗&#xff1f;以下是如何通过简单的步骤阻止和允许Windows防火墙中的程序。​ 一般来说&#xff0c;大多数用户永远不需要担心应用程序访问互联网。然而&#xff0c;在某些情况下&#xff0c;你需要限制应用程序访问互联网。 例如&#xff0c;有问题…

vue知识-03

购物车案例 要实现的功能&#xff1a; 1、计算商品总价格 2、全选框和取消全选框 3、商品数量的增加和减少 <body> <div id"app"><div class"row"><div class"col-md-6 col-md-offset-3"><h1 class"text-center…

TinyLog iOS v3.0接入文档

1.背景 为在线教育部提供高效、安全、易用的日志组件。 2.功能介绍 2.1 日志格式化 目前输出的日志格式如下&#xff1a; 日志级别/[YYYY-MM-DD HH:MM:SS MS] TinyLog-Tag: |线程| 代码文件名:行数|函数名|日志输出内容触发flush到文件的时机&#xff1a; 每15分钟定时触发…

【Spring 篇】走进SpringMVC的世界:舞动Web的激情

嗨&#xff0c;亲爱的小白们&#xff01;欢迎来到这篇关于SpringMVC的博客&#xff0c;让我们一起探索这个舞动Web的框架&#xff0c;感受它带来的激情和便利。在这个世界里&#xff0c;我们将学到SpringMVC的概述、开发步骤以及如何快速入门&#xff0c;一切都是如此的令人兴奋…

C# Winform翻牌子记忆小游戏

效果 源码 新建一个winform项目命名为Matching Game&#xff0c;选用.net core 6框架 并把Form1.cs代码修改为 using Timer System.Windows.Forms.Timer;namespace Matching_Game {public partial class Form1 : Form{private const int row 4;private const int col 4;p…

为什么光刻要用黄光

光刻是集成电路&#xff08;IC或芯片&#xff09;制造中的重要工艺之一。简单来说&#xff0c;它是通过使用光掩膜和光刻胶在基板上复制电路图案的过程。 基板将涂覆硅二氧化层绝缘层和光刻胶。光刻胶在被紫外光照射后可以容易地用显影剂溶解&#xff0c;然后在腐蚀后&#xf…

MongoDB Compass当前版本及历史版本下载安装

mongoDB compass 当前版本下载 官网 https://www.mongodb.com/try/download/compass 官网下载一般只能下载最新版本。 github https://github.com/mongodb-js/compass MongoDB Compass与MongoDB的版本对应关系 MongoDB CompassMongoDB1.9.12MongoDB 2.6.11 Community

Redis:原理速成+项目实战——Redis企业级项目实战终结篇(HyperLogLog实现UV统计)

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;Redis&#xff1a;原理速成项目实战——Redis实战14&#xff08;BitMap实现用户签到功能&#xff09; &#x1f4da;订阅专栏&am…

uniapp-uniCloud的基本使用(编写云存储的地区级联选择器)

目录 新建项目&#xff0c;创建 uniCloud 服务空间并关联 1. 新建项目 2. 创建 uniCloud 服务空间并关联 manifest.json内未配置Appld,请重新获取后再 云数据库的使用 城市选择和云数据库 介绍 云端数据 DB Schema概述 新建项目&#xff0c;创建 uniCloud 服务空间并关…

统计学-R语言-4.3

文章目录 前言直方图茎叶图箱线图练习 前言 本篇介绍的是数值型数据怎么进行数据可视化&#xff0c;本篇介绍的有直方图、茎叶图、箱线图。 直方图 直方图&#xff08;Histogram&#xff09;用于描述连续型变量的频数分布&#xff0c;实际应用中常用于考察变量的分布是否对称…

Java零基础——Vue基础篇

1.【熟悉】Vue简介 1.1 简介 它是一个构建用户界面单页面的框架 Vue是一个前端框架 https://www.pmdaniu.com/#file UI网站 UI 一般开发者使用蓝湖 工具 看着UI图 写接口 https://lanhuapp.com/web/#/item 是一个轻量级的MVVM&#xff08;Model-View-ViewModel&#xff…

maven管理使用

maven基本使用 一、简介二、配置文件三、项目结构maven基本标签实践(例子) 四、pom插件配置五、热部署六、maven 外部手动加载jar打包方式Maven上传私服或者本地 一、简介 基于Ant 的构建工具,Ant 有的功能Maven 都有,额外添加了其他功能.本地仓库:计算机中一个文件夹,自己定义…

Linux实操学习

Linux常用操作 一、帮助命令1. man1.1 基本语法1.2 快捷键1.3 注意事项 2. help2.1 基本语法2.2 注意事项 3. 常用快捷键 二、文件目录类1. 常规操作1.1 pwd1.2 cd1.3 ls 2. 文件夹操作2.1 mkdir2.2 rmdir 3. 文件操作3.1 touch3.2 cp3.3 rm3.4 mv 4. 文件查看4.1 cat4.2 more4…

国内外好用的 LLM 列表

视频来源&#xff1a;https://www.bilibili.com/video/BV1c64y157Qm/?vd_source1e841703c91b5b77fd20e5707bae49d2 下图是测试括号闭合能力的得分