图的访问(C++)
题目描述
给出 N 个点,M 条边的有向图,对于每个点 v,求 A(v) 表示从点 v 出发,能到达的编号最大的点。
输入格式
第 1 行 2 个整数 N,M,表示点数和边数。
接下来 M 行,每行 2 个整数 Ui,Vi,表示一条从 Ui 到 Vi 的有向边 (Ui,Vi)。点用 1,2,…,N 编号。
输出格式
一行 N 个整数 A(1),A(2),…,A(N)。
样例 #1
样例输入 #1
4 3
1 2
2 4
4 3
样例输出 #1
4 4 3 4
提示
对于 60% 的数据,1≤N,M≤103。
对于 100% 的数据,1≤N,M≤105。
#include<bits/stdc++.h>
using namespace std;
struct yjc {int nxt;int to;int dis;
} yjc[100001];
int num;
int head[100001];
int n, m, ans;
bool vis[100001];
void add(int f, int to) {num++;yjc[num].to = to;yjc[num].nxt = head[f];head[f] = num;
}
void dfs(int i) {if (vis[i] == true)return;ans = max(i, ans);vis[i] = true;for (int j = head[i]; j != 0; j = yjc[j].nxt) {int z = yjc[j].to;if (!vis[z]) dfs(z);}
}
void bfs(int i){queue<int >q;int start=i;q.push(start);vis[start]=1;while(!q.empty()){int now=q.front();ans=max(ans,now);if(ans==n)return;q.pop();for(int j=head[now];j!=0;j=yjc[j].nxt){int w=yjc[j].to;if(vis[w]==0) q.push(w),vis[w]=1;}}
}
int main() {cin >> n >> m;for (int i = 0; i < m; i++) {int x, y;cin >> x >> y;add(x, y);}for (int j = 1; j < n; j++) {ans = INT_MIN;memset(vis, false, sizeof(vis));bfs(j);cout << ans << ' ';}cout<<n<<' ';return 0;
}
相关文章:
图的访问(C++)
题目描述 给出 N 个点,M 条边的有向图,对于每个点 v,求 A(v) 表示从点 v 出发,能到达的编号最大的点。 输入格式 第 1 行 2 个整数 N,M,表示点数和边数。 接下来 M 行,每行 2 个整数 Ui,Vi,表…...
LeetCode做题记录(第二天)169. 多数元素
题目:169. 多数元素 标签:数组 哈希表 分治 计数 排序 题目信息: 思路一: 在题目中出现了计数,那我们就可以直接考虑考虑使用哈希表 unordered_map 即遍历的时候记录每个数的出现次数,当出现次数大于n/…...
Adobe XD中文设置指南:专业设计师的现场解答
Adobe XD是世界领先的在线合作UI设计工具。它摆脱了Sketch、Figma等传统设计软件对设备的依赖,使设计师可以随时随地使用任何设备打开网页浏览器,轻松实现跨平台、跨时空的设计合作。然后,为了提高国内设计师的使用体验,Adobe XD如…...
CentOS 7 安装Jenkins2.346.1(war方式安装)
既然想要安装Jenkins,肯定是先要从官网解读所需环境配置信息,如需了解更多自行查阅 https://www.jenkins.io/doc/book/installing/linux/ JDK17,Maven3.9 安装 先从官网分别下载JDK17与Maven3.9 下载好之后上传至服务器、并解压:…...
使用Java -jar运行就jar包时报异常:org.yaml.snakeyaml.error.YAMLException异常
Java运行就 .jar包时出现的 YAMLException 异常 我在本地环境测试时,使用 java -jar 命令运行 Java 可执行 .jar 包时,遇到了 org.yaml.snakeyaml.error.YAMLException: java.nio.charset.MalformedInputException: Input length 1 异常;这…...
golang实现的ab测试http代理工具
压测工具ab不能统计http请求的错误情况,包括http状态码错误和响应正文的错误关键字。 所以加层代理用于统计http错误情况,重在统计错误情况,而不是代理的性能,主要用于功能接口的测试,比如测试一下请求多少次接口会返…...
Maven学习——Maven的下载、安装与配置(详细攻略!)
目录 前言 1.下载与安装 2.配置Maven的环境变量 3.配置Maven的本地仓库 4. 配置Maven的镜像远程仓库 前言 我在之前写了一篇博客,是介绍Maven的基本概念和下载安装,但是由于篇幅过长,Maven的下载与安装写的并不详细🐶&#x…...
C#知识|账号管理系统-修改账号按钮功能的实现
哈喽,你好啊,我是雷工! 前边学习了通过选择条件查询账号的功能: 《提交查询按钮事件的编写》 本节继续学习练习C#,今天练习修改账号的功能实现。 以下为学习笔记。 01 实现功能 ①:从查询到的账号中,选择某一账号,然后点击【修改账号】按钮,将选中的信息获取显示到…...
bug等级和优先级
一、bug的等级 1、致命 这类bug是最严重的,通常导致系统无法运行、主要功能失效或严重资源不足。举例包括软件在安装过程中崩溃,导致无法完成安装;登录功能失效,用户无法验证身份进入系统;主要功能模块(如…...
记录|C# winform布局学习
目录 前言一、自适应布局Step1. 添加AutoAdaptWindowsSize类Step2. Form中引用Step3. 创建SizeChanged事件函数Step4. 在Fram.Disiger中添加 更新时间 前言 参考视频: C#5分钟winform快速自适应布局 参考文章: 其他参考: 写这篇文章ÿ…...
C/C++ json库
文章目录 一、介绍1.1 json 介绍 二、C/C json 库选型2.1 选型范围2.2 jsoncpp2.2.2 jsoncpp 编译和交叉编译 2.3 rapidjson2.4 nlohmann/json2.5 sonic-cpp 五、常见问题5.1 jsoncpp 中关于浮点数的控制和中文显示问题5.2 jsoncpp序列化double类型时精度损失问题的解决办法 一…...
C++案例四:简易记事本程序
文章目录 程序介绍代码说明包含必要的头文件主函数定义变量定义主循环显示菜单和读取选择处理用户选择程序介绍 编写一个简单的记事本程序,可以帮助用户添加和查看笔记。这个案例可以练习C++中的输入输出、向量(std::vector)、字符串处理(std::string)、以及简单的控制结…...
【VUE学习】day03-过滤器filter
VUE学习第三天 过滤器filter全局过滤器私有过滤器 过滤器filter 作用:常见的文本格式化使用场景:插值表达式、v-bind用法:{{msg | filterName}} ; v-bind:属性‘msg | filterName’ msg:需要格式化的文本信息(管道符前面的数据&a…...
技术成神之路:设计模式(八)责任链模式
介绍 责任链模式(Chain of Responsibility Pattern)是一种行为设计模式,它允许多个对象依次处理请求,避免请求的发送者和接收者之间的显式耦合。该模式通过将多个可能处理请求的对象连接成一条链,并沿着这条链传递请求…...
【Zynq UltraScale+ RFSoC】~~~
Zynq UltraScale RFSoC 系列为 5G 无线和射频级模拟应用引入了颠覆性的集成和架构突破,可直接支持整个 5G sub-6GHz 频段。这个创新系列现已开始批量生产。此设计演示展示了多通道(8T8R 或 16T16R)Zynq UltraScale RFSoC 评估工具工具工具&am…...
STM32之八:IIC通信协议
目录 1. IIC协议简介 1.1 主从模式 1.2 2根通信线 2. IIC协议时序 2.1 起始条件和终止条件 2.2 应答信号 2.3 发送一个字节 2.4 接收一个字节 3. IIC读写操作 3.1 写操作 3.2 读操作 1. IIC协议简介 IIC协议是一个半双工、同步、一主多从、多主多从的串行通用数据总…...
mysql的数据往hive进行上报时怎么保证数据的准确性和一致性
在将MySQL的数据往Hive进行上报时,确保数据的准确性和一致性可以通过下面一系列步骤来实现 一、准备工作 环境配置: 确保MySQL和Hive环境已经安装并配置好,且都处于可运行状态。检查Hadoop集群(Hive通常运行在Hadoop之上&#x…...
问题:4、商业保险与政策性保险的主要不同之处是:经营主体不同、经营目标不同、承保机制不同。 #学习方法#其他#学习方法
问题:4、商业保险与政策性保险的主要不同之处是:经营主体不同、经营目标不同、承保机制不同。 参考答案如图所示...
Getx学习笔记之中间件鉴权
目录 前言 一、实现步骤 1.添加依赖 2.创建鉴权中间件 3.定义路由 4.设置初始路由 5.模拟登陆状态 二、Getx鉴权步骤总结 三、本文demo示例 四、参考文章 前言 在 Flutter 中,使用 GetX 可以很方便地实现中间件鉴权(Authentication)…...
介绍 Elasticsearch 中的 Learning to Tank - 学习排名
作者:来自 Elastic Aurlien Foucret 从 Elasticsearch 8.13 开始,我们提供了原生集成到 Elasticsearch 中的学习排名 (learning to rank - LTR) 实现。LTR 使用经过训练的机器学习 (ML) 模型为你的搜索引擎构建排名功能。通常,该模型用作第二…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
