NOIP模拟赛 轰炸(bomb)
题目描述
有nnn座城市,城市之间建立了mmm条有向的地下通道。
你需要发起若干轮轰炸,每轮可以轰炸任意多的城市。但在每次轰炸城市中,不能同时存在两个城市i,ji,ji,j满足可以通过地下通道从城市iii到达城市jjj。你需要求出最少需要多少轮可以对每座城市都进行至少一次轰炸。
输入格式
第一行一个整数mmm,接下来mmm行每行两个整数a,ba,ba,b表示一条从aaa到bbb的单向边。
输出格式
一行一个整数表示答案。
样例输入
5 4
1 2
2 3
3 1
4 5
样例输出
3
数据范围
1≤n,m≤1061\leq n,m\leq 10^61≤n,m≤106
题解
题意即为每次可以轰炸任意多的城市,但不能有两个城市i,ji,ji,j满足i,ji,ji,j在同一条链上。
如果这个图没有环,那么显然答案为最长的一条链。这条链上每个点都轰炸一次。与此同时,其他链上的点也都轰炸一次,即可将所有城市都轰炸一次。用拓扑排序即可解决。
那如果有环呢?我们可以用求强连通分量的Tarjan算法,求出每个强连通分量,再把每个强连通分量都缩成一个点。此时的图已经没有环了,按上面的方法做就行了。
注意缩点之后,炸完一个点所需要的次数为这个点表示的强连通分量的大小。
时间复杂度为O(n)O(n)O(n)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,m,x,y,tot=0,dt=0,top=0,ans=0,d[N+5],l[N+5],r[N+5],st[N+5];
int ct=0,dfn[N+5],low[N+5],c[N+5],cnt[N+5],f[N+5];
vector<int>hv[N+5];
queue<int>q;
struct node{int x,y;
}w[N+5];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u){dfn[u]=low[u]=++dt;st[++top]=u;for(int i=r[u];i;i=l[i]){int v=d[i];if(!dfn[v]){dfs(v);low[u]=min(low[u],low[v]);}else if(!c[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){++ct;while(top>0){c[st[top]]=ct;hv[ct].push_back(st[top]);--top;if(st[top+1]==u) break;}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);w[i]=(node){x,y};add(x,y);}for(int i=1;i<=n;i++){if(!dfn[i]) dfs(i);}tot=0;memset(r,0,sizeof(r));for(int i=1;i<=m;i++){x=w[i].x;y=w[i].y;if(c[x]==c[y]) continue;add(c[x],c[y]);++cnt[c[y]];}for(int i=1;i<=ct;i++){if(!cnt[i]) q.push(i);}while(!q.empty()){int u=q.front();q.pop();f[u]+=hv[u].size();for(int i=r[u];i;i=l[i]){f[d[i]]=max(f[d[i]],f[u]);--cnt[d[i]];if(!cnt[d[i]]) q.push(d[i]);}}for(int i=1;i<=ct;i++){ans=max(ans,f[i]);}printf("%d",ans);return 0;
}
相关文章:
NOIP模拟赛 轰炸(bomb)
题目描述 有nnn座城市,城市之间建立了mmm条有向的地下通道。 你需要发起若干轮轰炸,每轮可以轰炸任意多的城市。但在每次轰炸城市中,不能同时存在两个城市i,ji,ji,j满足可以通过地下通道从城市iii到达城市jjj。你需要求出最少需要多少轮可以…...
Linux系统之安装PHP环境
Linux系统之安装PHP环境 一、PHP介绍1.PHP简介2.PHP优势3.php7版本特点二、本地环境介绍1.环境规划2.检查操作系统版本3.检查当前yum仓库三、安装PHP5.4版本1.查看可安装php版本2.使用yum安装php3.安装httpd服务4.关闭selinux和设置防火墙5.编辑index.php测试文件6.测试php环境…...

MySQL8的安装教程
MySQL8的安装教程 1.安装包的下载 如果不想去官网下载的话可以去百度网盘进行下载。 MySQL :: Download MySQL Community Server mysql-8.0.28-winx64.zip_免费高速下载|百度网盘-分享无限制 (baidu.com) 提取码:0001 2.解压 3.创建一个my.ini的文件 最好是创建…...

日入500+的程序员都在用的“接私活”平台
网上总说程序员的薪资很高,这我可就不同意了: 程序员的薪资哪里是很高,而是非常高!而会接私活的程序员更是能拿到更高的收入!作为一个程序员,这些接私活的网站一定要收藏起来,让你在“八小时外…...

MySQL表设计思路(一对多、多对多...)
要开始单独负责需求了,捋一捋表设计的思路。 文章目录一、MySQL中的数据类型二、一对一的关系设计二、一对多的关系设计三、多对多的关系设计四、经验总结一、MySQL中的数据类型 字符串类型 varchar:即variable char ,可边长度的字符串&#…...
内存对齐:C/C++编程中的重要性和技巧
C/C中的内存对齐前言基本概念 什么是内存对齐?内存对齐的定义内存对齐的作用数据类型的大小ARM 64 位架构和 x86_64 架构下的数据类型大小ARM 32 位架构下的数据类型大小内存对齐的边界填充字节的作用内存对齐的原理结构体中的内存对齐结构体的定义和使用结构体中成…...
C++ Primer第五版_第七章习题答案(41~50)
文章目录练习7.411、头文件2、源文件3、主函数练习7.42练习7.43练习7.44练习7.45练习7.46练习7.47练习7.48练习7.49练习7.50练习7.41 使用委托构造函数重新编写你的Sales_data 类,给每个构造函数体添加一条语句,令其一旦执行就打印一条信息。用各种可能的…...
python玄阶斗技--NumPy入门
目录 一.NumPy介绍 二.创建数组 1.一维数组创建 2.二维数组创建 3.zeros函数 4.ones函数 5.empty函数 6.arange函数 三.NumPy的数学操作 1.基本运算 2.矩阵运算 3.ndarray类的方法 四.数组堆叠 五.数组分隔 一.NumPy介绍 在这里对NumPy的介绍我不想扯太多…...

VR黑科技丨远离拥挤,VR直播开启沉浸式赏樱新姿势
春光兮婉转,珞樱兮盛绽,又是一年樱花季,全国各地大部分地区的樱花进入盛花期,尤其是武汉,东湖樱园踏青赏花的游人如织、摩肩擦踵,勾勒一幅“人人人人人人人花人人人人人”的盛景。 为了一睹樱花“芳容”&am…...
ts的一些用法
1.交叉类型 & ---多个类型属性的集合 1.1类型别名实现 type Person {name:string} type Children Person & {age:number} let newPerson:Children {// name:hahah,name:hhaah,age:18 } 1.2 接口类型实现 interface Inter1{name:string } interface Inter2{name:…...
云计算面试总结
shell脚本对日志进行备份 shell 对日志备份 #!/bin/bash if [ -d /log/bak/ ] || mkdir -p /log/bak/ thentar Pcf /log/bak/log_$(date %Y%m%d)$(date %H%M%S).tar.gz /var/log/*.logecho "干完!可以约会啦" fi存在的问题: 说的太快&a…...
(DP)买不到的数目【蓝桥杯】(裴蜀定理)
买不到的数目 小明开了一家糖果店。 他别出心裁:把水果糖包成4颗一包和7颗一包的两种。 糖果不能拆包卖。 小朋友来买糖的时候,他就用这两种包装来组合。 当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。 你可以用计算机测试一下&#…...
Docker使用DockerFile部署Go项目
Docker使用DockerFile部署Go项目1. 文章说明2. Go项目打包到Linux2.1 学习链接与知识点2.2. 打包生成 main 文件2.3 Docker部署Go项目1. 文章说明 目的:将打包生成的 main 文件,在Docker里面,使用Dockerfile文件,生成镜像与容器&…...
C++ Primer第五版_第七章习题答案(31~40)
文章目录练习7.31练习7.32练习7.33练习7.34练习7.35练习7.36练习7.37练习7.38练习7.29练习7.40练习7.31 定义一对类X 和Y,其中X 包含一个指向 Y 的指针,而Y 包含一个类型为 X 的对象。 class Y;class X{Y* y nullptr; };class Y{X x; };练习7.32 定义你…...

基于springboot实现学生成绩管理系统【源码+论文】分享
基于springboot实现学生成绩管理系统演示开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包&…...
Linux diff 命令
Linux diff 命令用于比较文件的差异。 diff 以逐行的方式,比较文本文件的异同处。如果指定要比较目录,则 diff 会比较目录中相同文件名的文件,但不会比较其中子目录。 语法 diff [-abBcdefHilnNpPqrstTuvwy][-<行数>][-C <行数&g…...
unity动画状态机
介绍: 动画状态机(Animation State Machine)是Unity中用于控制动画状态转换的工具,它由多个状态(State)和转换(Transition)组成,可以通过状态转换来控制动画的播放行为。…...

溯源(五)之攻击源的获取
溯源(一)之溯源的概念与意义 溯源(二)之 windows-还原攻击路径 溯源(三)之Linux-入侵排查 溯源(四)之流量分析-Wireshark使用 溯源整体流程的思维导图 攻击源的获取 1、获取哪些数…...
【redis】redis淘汰策略
一、说明 1.redis key没有设置过期时间被redis主动删除了 2.当redis已用内存超过maxmemory限定时,触发主动清理策略 3.主动清理策略在redis4.0之前一共实现了6种内存淘汰策略,在4.0之后,增加了2种,总共8种 二、淘汰策略 2.1 针对…...
指针和数组(二)
目录 指针和数组 数组名和指针的区别 多维数组 数组指针 语法 作用 内存大小 自增运算 【】运算 指针和数组 结论:数组的本质就是指针。数组的【】运算同样可以用指针来运算 证明 C代码 int array[5];int* ptr{ &array[0] };*ptr 5;array[0] 5;arr…...

SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...

鸿蒙Navigation路由导航-基本使用介绍
1. Navigation介绍 Navigation组件是路由导航的根视图容器,一般作为Page页面的根容器使用,其内部默认包含了标题栏、内容区和工具栏,其中内容区默认首页显示导航内容(Navigation的子组件)或非首页显示(Nav…...

aurora与pcie的数据高速传输
设备:zynq7100; 开发环境:window; vivado版本:2021.1; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程,pc通过pcie传输给fpga,fpga再通过aur…...