图的访问(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) 模型为你的搜索引擎构建排名功能。通常,该模型用作第二…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
