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…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...

使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...