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

每天一题:洛谷P2002 消息扩散

题目背景

本场比赛第一题,给个简单的吧,这 100 分先拿着。

题目描述

有 n 个城市,中间有单向道路连接,消息会沿着道路扩散,现在给出 n 个城市及其之间的道路,问至少需要在几个城市发布消息才能让这所有 n 个城市都得到消息。

输入格式

第一行两个整数 n,m,表示 n 个城市,m 条单向道路。

以下 m 行,每行两个整数 b,e 表示有一条从 b 到 e 的道路,道路可以重复或存在自环。

输出格式

一行一个整数,表示至少要在几个城市中发布消息。

输入输出样例

输入 #1

5 4
1 2
2 1
2 3
5 1

输出 #1

2

说明/提示

【样例解释 #1】

样例中在 4,5 号城市中发布消息。

【数据范围】

对于 20% 的数据,n≤200;
对于 40% 的数据,n≤2000;
对于 100% 的数据,1≤n≤10^{5},1≤m≤5×10^{5}

解题方法

有没有感觉此题跟刻录光盘特像,都是求强连通分量中入度为零的分量,那么代码就可以轻松自在地写出来啦~

当然要注意,由于存在自环,所以在输入的时候要进行去环。

代码嘛,这里就不放了~~~~~~~~~~~~

相关文章:

每天一题:洛谷P2002 消息扩散

题目背景 本场比赛第一题,给个简单的吧,这 100 分先拿着。 题目描述 有 n 个城市,中间有单向道路连接,消息会沿着道路扩散,现在给出 n 个城市及其之间的道路,问至少需要在几个城市发布消息才能让这所有 …...

【深度学习】用LSTM写诗,生成式的方式写诗系列之一

Epoch 4: 100%|███████████████████████████████████████████████████████████| 63/63 [00:07<00:00, 8.85batch/s, acc18.5, loss5.8] [5] loss: 5.828, accuracy: 18.389 , lr:0.001000 Epoch 5: 100%|███…...

HomeAssistant自定义组件学习-【二】

#要说的话# 前面把中盛科技的控制器组件写完了。稍稍熟悉了一些HA&#xff0c;现在准备写窗帘控制组件&#xff0c;构想的东西会比较多&#xff0c;估计有些难度&#xff0c;过程会比较长&#xff0c;边写边记录吧&#xff01; #设备和场景环境# 使用的是Novo的电机&#xf…...

如何看待AI技术的应用前景?

文章目录 如何看待AI技术的应用前景引言AI技术的现状1. AI的定义与分类2. 当前AI技术的应用领域 AI技术的应用前景1. 经济效益2. 社会影响3. 技术进步 AI技术应用面临的挑战1. 数据隐私与安全2. 可解释性与信任3. 技能短缺与就业影响 AI技术的未来发展方向1. 人工智能的伦理与法…...

Unity中的屏幕坐标系

获得视口宽高 拖动视口会改变屏幕宽高数值 MousePosition 屏幕坐标系的原点在左下角&#xff0c;MousePosition返回Z为0也就是纵深为0的Vector3 但是如果鼠标超出屏幕范围不会做限制&#xff0c;所以可能出现负数或者大于屏幕宽高的情况&#xff0c;做鼠标拖拽物体时需要注…...

标题点击可跳转网页

要实现点击标题跳转到网页的功能&#xff0c;你可以在Vue组件中使用<a>标签&#xff08;锚点标签&#xff09;并设置href属性为网页的URL。如果你希望使用uni-app的特性来控制页面跳转&#xff0c;可以使用uni.navigateTo方法&#xff08;这适用于uni-app环境&#xff0c…...

易语言模拟真人动态生成鼠标滑动路径

一.简介 鼠标轨迹算法是一种模拟人类鼠标操作的程序&#xff0c;它能够模拟出自然而真实的鼠标移动路径。 鼠标轨迹算法的底层实现采用C/C语言&#xff0c;原因在于C/C提供了高性能的执行能力和直接访问操作系统底层资源的能力。 鼠标轨迹算法具有以下优势&#xff1a; 模拟…...

Linux:生态与软件安装

文章目录 前言一、Linux下安装软件的方案二、包管理器是什么&#xff1f;三、生态问题相关的理解1. 什么操作系统是好的操作系统&#xff1f;2. 什么是生态&#xff1f;3. 软件包是谁写的&#xff1f;这些工程师为什么要写&#xff1f;钱的问题怎么解决? 四、我的服务器怎么知…...

R 语言与其他编程语言的区别

R 语言与其他编程语言的区别 R 语言作为一种专门用于统计计算和图形的编程语言&#xff0c;与其他编程语言相比有一些独特的特点和区别。本文将详细介绍这些区别&#xff0c;帮助你更好地理解 R 语言的优势和适用场景。 1. 专为统计和数据分析设计 统计功能 内置统计函数&…...

RC低通滤波器Bode图分析(传递函数零极点)

RC低通滤波器 我们使得R1K&#xff0c;C1uF&#xff1b;电容C的阻抗为Xc&#xff1b; 传递函数 H ( s ) u o u i X C X C R 1 s C 1 s C R 1 1 s R C &#xff08;其中 s j ω &#xff09; H(s)\frac{u_{o} }{u_{i} } \frac{X_{C} }{X_{C}R} \frac{\frac{1}{sC} }{\…...

基于深度学习的网络入侵检测

基于深度学习的网络入侵检测是一种利用深度学习技术对网络流量进行实时监测与分析的方法&#xff0c;旨在识别并防范网络攻击和恶意活动。随着网络环境日益复杂&#xff0c;传统的入侵检测系统&#xff08;IDS&#xff09;在面对不断变化的攻击模式时&#xff0c;往往难以保持高…...

《构建一个具备从后端数据库获取数据并再前端显示的内容页面:前后端实现解析》

一、前端页面&#xff1a;布局与功能 1. 页面结构 我们先来看前端页面的 HTML 结构&#xff0c;它主要由以下几个部分组成&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewp…...

Rust 力扣 - 59. 螺旋矩阵 II

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 使用一个全局变量current记录当前遍历到的元素的值 我们只需要一圈一圈的从外向内遍历矩阵&#xff0c;每一圈遍历顺序为上边、右边、下边、左边&#xff0c;每遍历完一个元素后current 我们需要注意的是如果上…...

2.4w字 —TS入门教程

目录 1. 什么是TS 2. TS基本使用 3 TS基础语法 3.1 基础类型约束 3.11 string&#xff0c;number&#xff0c;boolean&#xff0c; null和undefined 3.12 any 3.13 unknown 3.14 void 3.15 数组 3.16 对象 3.2 函数的约束 3.21 普通写法 3.22 函数表达式 3.22 可选…...

java: 未结束的字符文字 报错及解决:将编码全部改为UTF-8或者GBK

报错&#xff1a; 解决&#xff1a; 将编码都改成UTF-8或者GBK&#xff1a;...

Android平台RTSP转RTMP推送之采集麦克风音频转发

技术背景 RTSP转RTMP推送&#xff0c;好多开发者第一想到的是采用ffmpeg命令行的形式&#xff0c;如果对ffmpeg比较熟&#xff0c;而且产品不要额外的定制和更高阶的要求&#xff0c;未尝不可&#xff0c;如果对产品稳定性、时延、断网重连等有更高的技术诉求&#xff0c;比较…...

认证鉴权框架之—sa-token

一、概述 Satoken 是一个 Java 实现的权限认证框架&#xff0c;它主要用于 Web 应用程序的权限控制。Satoken 提供了丰富的功能来简化权限管理的过程&#xff0c;使得开发者可以更加专注于业务逻辑的开发。 二、逻辑流程 1、登录认证 &#xff08;1&#xff09;、创建token …...

Spring源码(十一):Spring MVC之DispatchServlet

本篇重点在于分析Spring MVC与Servlet标准的整合&#xff0c;下节将详细讨论Spring MVC的启动/加载流程、处理请求的具体流程。 一、介绍 Spring框架提供了构建Web应用程序的全功能MVC模块。通过策略接口 &#xff0c;Spring框架是高度可配置的&#xff0c;而且支持多种视图技…...

gitbash简单操作

https://blog.csdn.net/qq_42363495/article/details/104878170 工作区(空间)--暂存区--本地仓库--远程仓库 方法一&#xff1a;创建一个新的分支master&#xff0c;且远程库里没有该分支 只要将.gitignore文件放在文件夹下就可以&#xff0c;.gitignore是文本文档形式的文件…...

pnpm install安装element-plus的版本跟package.json指定的版本不一样

pnpm安装的版本不同于package.json中指定的版本可能是由于以下几种情况导致的&#xff1a; 依赖项冲突&#xff1a;当项目依赖的不同模块或库之间存在版本冲突时&#xff0c;pnpm可能会安装与package.json中指定的版本不同的版本。这可能是因为其他依赖项指定了不同的版本&…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...

python打卡第47天

昨天代码中注意力热图的部分顺移至今天 知识点回顾&#xff1a; 热力图 作业&#xff1a;对比不同卷积层热图可视化的结果 def visualize_attention_map(model, test_loader, device, class_names, num_samples3):"""可视化模型的注意力热力图&#xff0c;展示模…...

当下AI智能硬件方案浅谈

背景&#xff1a; 现在大模型出来以后&#xff0c;打破了常规的机械式的对话&#xff0c;人机对话变得更聪明一点。 对话用到的技术主要是实时音视频&#xff0c;简称为RTC。下游硬件厂商一般都不会去自己开发音视频技术&#xff0c;开发自己的大模型。商用方案多见为字节、百…...

2025 后端自学UNIAPP【项目实战:旅游项目】7、景点详情页面【完结】

1、获取景点详情的请求【my_api.js】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http(/login/getWXSessionKey, {code,avatar}); };//…...

Java求职者面试:微服务技术与源码原理深度解析

Java求职者面试&#xff1a;微服务技术与源码原理深度解析 第一轮&#xff1a;基础概念问题 1. 请解释什么是微服务架构&#xff0c;并说明其优势和挑战。 微服务架构是一种将单体应用拆分为多个小型、独立的服务的软件开发方法。每个服务都运行在自己的进程中&#xff0c;并…...

民锋视角下的资金流效率与账户行为建模

民锋视角下的资金流效率与账户行为建模 在当前复杂多变的金融环境中&#xff0c;资金流效率已成为衡量一家金融服务机构专业能力的重要指标。民锋在账户管理与资金调配的实战经验中&#xff0c;逐步建立起一套以资金流路径为核心的行为建模方法&#xff0c;用以评估客户行为、交…...

设计模式-观察着模式

观察者模式 观察者模式 (Observer Pattern) 是一种行为型设计模式&#xff0c;它定义了对象之间一种一对多的依赖关系&#xff0c;当一个对象&#xff08;称为主题或可观察者&#xff09;的状态发生改变时&#xff0c;所有依赖于它的对象&#xff08;称为观察者&#xff09;都…...