图的访问(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) 模型为你的搜索引擎构建排名功能。通常,该模型用作第二…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
