图的访问(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) 模型为你的搜索引擎构建排名功能。通常,该模型用作第二…...
3分钟快速修复机械键盘连击问题:终极解决方案指南
3分钟快速修复机械键盘连击问题:终极解决方案指南 【免费下载链接】KeyboardChatterBlocker A handy quick tool for blocking mechanical keyboard chatter. 项目地址: https://gitcode.com/gh_mirrors/ke/KeyboardChatterBlocker KeyboardChatterBlocker是…...
遥感影像配准总对不齐?OpenCV+RST+PROJ4三重坐标系对齐实战(附WGS84→UTM→影像本地坐标的转换矩阵速查表)
第一章:Shell脚本的基本语法和命令Shell脚本是Linux/Unix系统自动化任务的核心工具,以可执行文本文件形式存在,由Bash等shell解释器逐行解析运行。其语法简洁但严谨,对空格、分号、引号和换行符敏感,需严格遵循语法规则…...
23种设计模式 - 组合模式(Composite)
组合模式(Composite)—— 文件夹套文件夹,统一操作 大白话解释 你的电脑里: 📄 文件(不能再包含东西)📁 文件夹(可以装文件,也可以装文件夹) &…...
重庆灌浆料销售厂家怎么联系
在重庆的建筑工程领域,灌浆料的应用十分广泛。然而,众多重庆灌浆料厂家的市场状况究竟如何?又存在哪些痛点呢?市场现状:鱼龙混杂目前,重庆灌浆料市场厂家众多,但质量参差不齐。行业权威报告显示…...
域环境基础知识
Active Directory(AD) 域控制器功能: 集中管理所有域用户统一身份认证组策略分发资源访问控制 Windows Server域环境搭建 推荐版本: Windows Server 2003Windows Server 2008Windows Server 2012 域环境组成: 域控制器…...
这次终于选对了!降AI率软件深度测评与推荐
2026年真正好用的AI论文降重与改写工具,核心看降重效果、去AI味、格式保留、学术适配四大指标。综合实测,千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队,覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 …...
OpenClaw终端增强:Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF实现命令行智能补全与解释
OpenClaw终端增强:Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF实现命令行智能补全与解释 1. 为什么需要智能终端助手 作为每天与终端打交道的开发者,我经常陷入这样的困境:面对复杂的docker compose命令需要反复查阅文档…...
《QGIS快速入门与应用基础》239:指北针样式选择(预设/自定义)
作者:翰墨之道,毕业于国际知名大学空间信息与计算机专业,获硕士学位,现任国内时空智能领域资深专家、CSDN知名技术博主。多年来深耕地理信息与时空智能核心技术研发,精通 QGIS、GrassGIS、OSG、OsgEarth、UE、Cesium、OpenLayers、Leaflet、MapBox 等主流工具与框架,兼具…...
如何快速部署Uvicorn ASGI服务器到AWS Lightsail:终极云服务器配置指南 [特殊字符]
如何快速部署Uvicorn ASGI服务器到AWS Lightsail:终极云服务器配置指南 🚀 【免费下载链接】uvicorn An ASGI web server, for Python. 🦄 项目地址: https://gitcode.com/GitHub_Trending/uv/uvicorn Uvicorn是一个轻量级、高性能的A…...
5大核心功能重塑Sketch效率:RenameIt批量命名工具的流程优化实践
5大核心功能重塑Sketch效率:RenameIt批量命名工具的流程优化实践 【免费下载链接】RenameIt Keep your Sketch files organized, batch rename layers and artboards. 项目地址: https://gitcode.com/gh_mirrors/re/RenameIt 在现代UI/UX设计工作流中&#x…...
