当前位置: 首页 > news >正文

图的访问(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 个点&#xff0c;M 条边的有向图&#xff0c;对于每个点 v&#xff0c;求 A(v) 表示从点 v 出发&#xff0c;能到达的编号最大的点。 输入格式 第 1 行 2 个整数 N,M&#xff0c;表示点数和边数。 接下来 M 行&#xff0c;每行 2 个整数 Ui,Vi&#xff0c;表…...

LeetCode做题记录(第二天)169. 多数元素

题目&#xff1a;169. 多数元素 标签&#xff1a;数组 哈希表 分治 计数 排序 题目信息&#xff1a; 思路一&#xff1a; 在题目中出现了计数&#xff0c;那我们就可以直接考虑考虑使用哈希表 unordered_map 即遍历的时候记录每个数的出现次数&#xff0c;当出现次数大于n/…...

Adobe XD中文设置指南:专业设计师的现场解答

Adobe XD是世界领先的在线合作UI设计工具。它摆脱了Sketch、Figma等传统设计软件对设备的依赖&#xff0c;使设计师可以随时随地使用任何设备打开网页浏览器&#xff0c;轻松实现跨平台、跨时空的设计合作。然后&#xff0c;为了提高国内设计师的使用体验&#xff0c;Adobe XD如…...

CentOS 7 安装Jenkins2.346.1(war方式安装)

既然想要安装Jenkins&#xff0c;肯定是先要从官网解读所需环境配置信息&#xff0c;如需了解更多自行查阅 https://www.jenkins.io/doc/book/installing/linux/ JDK17&#xff0c;Maven3.9 安装 先从官网分别下载JDK17与Maven3.9 下载好之后上传至服务器、并解压&#xff1a…...

使用Java -jar运行就jar包时报异常:org.yaml.snakeyaml.error.YAMLException异常

Java运行就 .jar包时出现的 YAMLException 异常 我在本地环境测试时&#xff0c;使用 java -jar 命令运行 Java 可执行 .jar 包时&#xff0c;遇到了 org.yaml.snakeyaml.error.YAMLException: java.nio.charset.MalformedInputException: Input length 1 异常&#xff1b;这…...

golang实现的ab测试http代理工具

压测工具ab不能统计http请求的错误情况&#xff0c;包括http状态码错误和响应正文的错误关键字。 所以加层代理用于统计http错误情况&#xff0c;重在统计错误情况&#xff0c;而不是代理的性能&#xff0c;主要用于功能接口的测试&#xff0c;比如测试一下请求多少次接口会返…...

Maven学习——Maven的下载、安装与配置(详细攻略!)

目录 前言 1.下载与安装 2.配置Maven的环境变量 3.配置Maven的本地仓库 4. 配置Maven的镜像远程仓库 前言 我在之前写了一篇博客&#xff0c;是介绍Maven的基本概念和下载安装&#xff0c;但是由于篇幅过长&#xff0c;Maven的下载与安装写的并不详细&#x1f436;&#x…...

C#知识|账号管理系统-修改账号按钮功能的实现

哈喽,你好啊,我是雷工! 前边学习了通过选择条件查询账号的功能: 《提交查询按钮事件的编写》 本节继续学习练习C#,今天练习修改账号的功能实现。 以下为学习笔记。 01 实现功能 ①:从查询到的账号中,选择某一账号,然后点击【修改账号】按钮,将选中的信息获取显示到…...

bug等级和优先级

一、bug的等级 1、致命 这类bug是最严重的&#xff0c;通常导致系统无法运行、主要功能失效或严重资源不足。举例包括软件在安装过程中崩溃&#xff0c;导致无法完成安装&#xff1b;登录功能失效&#xff0c;用户无法验证身份进入系统&#xff1b;主要功能模块&#xff08;如…...

记录|C# winform布局学习

目录 前言一、自适应布局Step1. 添加AutoAdaptWindowsSize类Step2. Form中引用Step3. 创建SizeChanged事件函数Step4. 在Fram.Disiger中添加 更新时间 前言 参考视频&#xff1a; C#5分钟winform快速自适应布局 参考文章&#xff1a; 其他参考&#xff1a; 写这篇文章&#xff…...

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 作用&#xff1a;常见的文本格式化使用场景&#xff1a;插值表达式、v-bind用法&#xff1a;{{msg | filterName}} ; v-bind:属性‘msg | filterName’ msg:需要格式化的文本信息&#xff08;管道符前面的数据&a…...

技术成神之路:设计模式(八)责任链模式

介绍 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为设计模式&#xff0c;它允许多个对象依次处理请求&#xff0c;避免请求的发送者和接收者之间的显式耦合。该模式通过将多个可能处理请求的对象连接成一条链&#xff0c;并沿着这条链传递请求…...

【Zynq UltraScale+ RFSoC】~~~

Zynq UltraScale RFSoC 系列为 5G 无线和射频级模拟应用引入了颠覆性的集成和架构突破&#xff0c;可直接支持整个 5G sub-6GHz 频段。这个创新系列现已开始批量生产。此设计演示展示了多通道&#xff08;8T8R 或 16T16R&#xff09;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进行上报时&#xff0c;确保数据的准确性和一致性可以通过下面一系列步骤来实现 一、准备工作 环境配置&#xff1a; 确保MySQL和Hive环境已经安装并配置好&#xff0c;且都处于可运行状态。检查Hadoop集群&#xff08;Hive通常运行在Hadoop之上&#x…...

问题:4、商业保险与政策性保险的主要不同之处是:经营主体不同、经营目标不同、承保机制不同。 #学习方法#其他#学习方法

问题&#xff1a;4、商业保险与政策性保险的主要不同之处是&#xff1a;经营主体不同、经营目标不同、承保机制不同。 参考答案如图所示...

Getx学习笔记之中间件鉴权

目录 前言 一、实现步骤 1.添加依赖 2.创建鉴权中间件 3.定义路由 4.设置初始路由 5.模拟登陆状态 二、Getx鉴权步骤总结 三、本文demo示例 四、参考文章 前言 在 Flutter 中&#xff0c;使用 GetX 可以很方便地实现中间件鉴权&#xff08;Authentication&#xff09…...

介绍 Elasticsearch 中的 Learning to Tank - 学习排名

作者&#xff1a;来自 Elastic Aurlien Foucret 从 Elasticsearch 8.13 开始&#xff0c;我们提供了原生集成到 Elasticsearch 中的学习排名 (learning to rank - LTR) 实现。LTR 使用经过训练的机器学习 (ML) 模型为你的搜索引擎构建排名功能。通常&#xff0c;该模型用作第二…...

变压器绕组类型 | 高频变压器绕制要点

注&#xff1a;本文为 “变压器绕制” 相关合辑。 英文引文&#xff0c;机翻未校。 如有内容异常&#xff0c;请看原文。 图片清晰度受引文原图所限。 变压器绕组类型&#xff1a;圆筒式、螺旋式、交叉式与饼式绕组 Types of Transformer Windings: Cylindrical, Helical, Cro…...

别再瞎猜了!YOLOv8 模型缩放(width_multiple)与通道计算(c1,c2)的完整逻辑

YOLOv8模型通道计算与宽度系数的工程化实践指南 在移动端部署YOLOv8模型时&#xff0c;许多工程师会遇到一个典型困境&#xff1a;明明按照官方文档调整了width_multiple参数&#xff0c;却发现模型要么计算量超出预期&#xff0c;要么精度断崖式下跌。这背后其实隐藏着YOLOv8通…...

玩转AI!用FastAPI+RAG轻松构建智能文档问答系统,代码、文档全公开!

在企业数字化转型的浪潮中&#xff0c;我们常遇到这样一个痛点&#xff1a;海量的业务文档、研究报告、技术手册堆积如山&#xff0c;当需要从中寻找某个特定答案时&#xff0c;员工往往要花费数小时甚至数天进行翻阅。这不仅是效率的浪费&#xff0c;更是知识资产沉睡的体现**…...

用ChatTTS打造你的专属AI语音助手:从音色定制到批量合成音频的完整工作流

用ChatTTS打造你的专属AI语音助手&#xff1a;从音色定制到批量合成音频的完整工作流 在内容创作领域&#xff0c;音频正成为越来越重要的媒介形式。无论是知识付费课程的讲解、播客节目的制作&#xff0c;还是智能设备的语音交互&#xff0c;一个稳定、个性化的语音合成系统都…...

浙政钉应用监控埋点参数(bid, sapp_id)到底去哪找?一份给开发者的沟通指南

浙政钉应用监控埋点参数获取实战指南&#xff1a;从沟通到落地的全流程解析 在政务数字化进程中&#xff0c;浙政钉作为重要的政务协同平台&#xff0c;其应用监控埋点数据的准确采集直接影响着后续的数据分析和决策支持。然而&#xff0c;许多开发团队在实际项目中常常陷入参数…...

本地部署 Ollama + DeepSeek 完整指南:免费跑大模型,数据不出本地

本地部署 Ollama DeepSeek 完整指南&#xff1a;免费跑大模型&#xff0c;数据不出本地不花一分钱&#xff0c;不用科学上网&#xff0c;在自己电脑上跑 DeepSeek 大模型&#xff0c;这篇教程手把手带你搞定一、为什么要本地部署&#xff1f; 很多人用 AI 工具都是调用云端 AP…...

光场相机入门:Macro Pixel与SAI如何让你的照片秒变3D(附Python代码示例)

光场相机实战指南&#xff1a;用Macro Pixel与SAI技术打造沉浸式3D影像 当你第一次看到光场相机拍摄的照片能在屏幕上自由切换焦点时&#xff0c;那种震撼感就像发现了摄影的新维度。这背后是Macro Pixel和SAI两项核心技术的完美配合——它们让静态图像拥有了动态的视角选择能力…...

ICML 2023亚马逊论文速览:自适应计算与差分隐私

机器学习 某机构在ICML 2023会议论文速览 在一系列主题中&#xff0c;某机构的研究融合了理论与实践的探索。 会议 ICML 2023 在今年的国际机器学习大会&#xff08;ICML&#xff09;上&#xff0c;某机构的研究人员发表了多篇关于赌博机问题和差分隐私的论文&#xff0c;这两个…...

springboot汽车配件商城销售管理系统

目录系统架构设计数据库设计核心功能实现销售管理模块库存预警功能报表统计模块系统测试策略部署方案项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作系统架构设计 采用SpringBoot作为后端框架&#xff0c;搭配MyBatis或JPA实现…...

douyin-downloader:智能化解构无水印视频批量采集的技术方案

douyin-downloader&#xff1a;智能化解构无水印视频批量采集的技术方案 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 在数字内容爆炸的时代&#xff0c;如何高效获取高质量视频素材成为内容创作者、研究者…...