P3916 图的遍历(Tarjan缩点和反向建边)
P3916 图的遍历 - 洛谷 | 计算机科学教育新生态

写法一:Tarjan
思路:先运用Tarjan算法得到每个连通块中最大的编号,然后对每个连通块进行缩点重新建图,进行dfs,得到缩点后的连通块能够达到的最大编号。
Code:
constexpr int N=1e5+5,mod=1e9+7;int a[N],dfn[N],stk[N],low[N],top,scc[N],cnt,tot;
int n,m,instack[N],ma[N],sz[N];
bool st[N];
int x[N],y[N];
vector<int> e[N],g[N];void Tarjan(int u)
{stk[++top]=u,instack[u]=1;low[u]=dfn[u]=++tot;for(auto t:e[u]){if(!dfn[t]){Tarjan(t);low[u]=min(low[u],low[t]);}else if(instack[t]) low[u]=min(low[u],dfn[t]);}if(low[u]==dfn[u]){cnt++; int y;//cout<<"____"<<cnt<<' '<<u<<endl;do{y=stk[top--]; instack[y]=0;scc[y]=cnt;// cout<<"____"<<cnt<<' '<<y<<endl;ma[cnt]=max(ma[cnt],y);}while(u!=y);}
}void dfs(int u)
{if(a[u]) return ;a[u]=ma[u];// cout<<u<<' '<<a[u]<<' '<<g[u].size()<<endl;for(auto t:g[u]){if(!a[t]){dfs(t);}a[u]=max(a[u],a[t]);// cout<<u<<' '<<t<<' '<<a[u]<<endl;}
}
void solve()
{cin>>n>>m;for(int i=0;i<m;i++){cin>>x[i]>>y[i];e[x[i]].push_back(y[i]);}for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);for(int i=0;i<m;i++){if(scc[x[i]]==scc[y[i]]) continue;g[scc[x[i]]].push_back(scc[y[i]]);}for(int i=1;i<=cnt;i++){if(!a[i]) dfs(i);}for(int i=1;i<=n;i++)cout<<a[scc[i]]<<' ';
}
写法二:反向建图
既然要计算每个点能走到的最大编号,我们可以直接从大编号 开始搜索与它关联的路径,该路径上的点均为大编号。
Code:
constexpr int N=1e5+5,mod=1e9+7;int a[N],n,m;
vector<int> e[N];void dfs(int u,int i)
{if(a[u]) return ;a[u]=i;for(auto t:e[u]){if(!a[t]){dfs(t,i);}}}
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;e[b].push_back(a);}for(int i=n;i;i--)if(!a[i]) dfs(i,i);for(int i=1;i<=n;i++) cout<<a[i]<<' ';
}
相关文章:
P3916 图的遍历(Tarjan缩点和反向建边)
P3916 图的遍历 - 洛谷 | 计算机科学教育新生态 写法一:Tarjan 思路:先运用Tarjan算法得到每个连通块中最大的编号,然后对每个连通块进行缩点重新建图,进行dfs,得到缩点后的连通块能够达到的最大编号。 Code: conste…...
Android13 允许桌面自动旋转
一)需求-场景 Android13 实现允许桌面自动旋转 Android13 版本开始后,支持屏幕自动旋转,优化体验和兼容性,适配不同屏幕 主界面可自动旋转 二)参考资料 android framework13-launcher3【06手机旋转问题】 Launcher默…...
cocotb value cocotb—基础语法对照篇
cocotb—基础语法对照篇 import cocotb from cocotb.triggers import Timer from adder_model import adder_model from cocotb.clock import Clock from cocotb.triggers import RisingEdge import randomcocotb.test() async def adder_basic_test(dut):"""Te…...
001-SpringBoot整合日志
SpringBoot整合日志 一、引入依赖二、配置 application.yml三、配置文件 logback.xml四、配置文件 WebConfigurerAdapter五、配置常量文件六、配置拦截器七、效果展示一、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId&…...
【Java基础面试题011】什么是Java中的自动装箱和拆箱?
相关知识补充:《Java从入门到精通(JDK17版)》_尚硅谷电子书.pdf Autism_Btkrsr/Blog_md_to_pdf - 码云 - 开源中国 (gitee.com) 回答重点 自动装箱:Java编译器自动将基本数据类型转换为包装类型 自动拆箱:Java编译器自动将包装类转换为基…...
ERROR in [eslint] Invalid Options ‘extensions‘ has been removed.
看着这个报错 感觉是版本不对引起的 ERROR in [eslint] Invalid Options: - Unknown options: extensions - extensions has been removed. ERROR in Error: Child compilation failed: [eslint] Invalid Options: - Unknown options: extensions - extensions has b…...
消息传递神经网络(Message Passing Neural Networks, MPNN)
消息传递神经网络(Message Passing Neural Networks, MPNN) 一、引言二、消息传递框架概述1.消息传递阶段(1)消息生成与传播-message(2)消息聚合-aggregate(3)消息更新-update&#…...
常用图像变换方法
伽马变换: void gamma_transform(cv::Mat &img, double gamma) {cv::Mat normalized;img.convertTo(normalized, CV_64F...
从被动响应到主动帮助,ProActive Agent开启人机交互新篇章
在人工智能领域,我们正见证着一场革命性的变革。传统的AI助手,如ChatGPT,需要明确的指令才能执行任务。但现在,清华大学联合面壁智能等团队提出了一种全新的主动式Agent交互范式——ProActive Agent,它能够主动观察环境…...
力扣hot100道【贪心算法后续解题方法心得】(三)
力扣hot100道【贪心算法后续解题方法心得】 十四、贪心算法关键解题思路1、买卖股票的最佳时机2、跳跃游戏3、跳跃游戏 | |4、划分字母区间 十五、动态规划什么是动态规划?关键解题思路和步骤1、打家劫舍2、01背包问题3、完全平方式4、零钱兑换5、单词拆分6、最长递…...
工业齐套管理虚拟现实仿真模拟软件
工业齐套管理虚拟现实仿真模拟软件是与法国最大的汽车制造商合作开发的一款虚拟现实仿真模拟软件,借助身临其境的虚拟现实环境,无需停止生产线,即可模拟仓库和提货区域。 工业齐套管理虚拟现实仿真模拟软件不仅适用于汽车工业,安全…...
ARP表、MAC表、路由表的区别和各自作用
文章目录 ARP表、MAC表、路由表的区别和各自作用同一网络内:ARP表request - 请求reply - 响应 MAC地址在同一网络内,交换机如何工作? 不同网络路由表不同网络通信流程PC1到路由器路由器到PC2流程图 简短总结 ARP表、MAC表、路由表的区别和各自作用 拓扑图如下: 同一网络内:…...
Android 使用OpenGLES + MediaPlayer 获取视频截图
概述 Android 获取视频缩略图的方法通常有: ContentResolver: 使用系统数据库MediaMetadataRetriever: 这个是android提供的类,用来获取本地和网络media相关文件的信息ThumbnailUtils: 是在android2.2(api8)之后新增的一个,该类为…...
浏览器的事件循环机制
浏览器和Node的事件循环机制 引言浏览器的事件循环机制 引言 由于JS是单线程的脚本语言,所以在同一时间只能做一件事情,当遇到多个任务时,我们不可能一直等待任务完成,这会造成巨大的资源浪费。为了协调时间,用户交互…...
Z2400032基于Java+Mysql+SSM的校园在线点餐系统的设计与实现 代码 论文
在线点餐系统 1.项目描述2. 技术栈3. 项目结构后端前端 4. 功能模块5. 项目实现步骤注意事项 6.界面展示7.源码获取 1.项目描述 本项目旨在开发一个校园在线点餐系统,通过前后端分离的方式,为在校学生提供便捷的餐厅点餐服务,同时方便餐厅和…...
k8s使用的nfs作为sc。
k8s使用的nfs作为sc。 当前出现一个问题: 1.有一个pod他是通过流进行文件解压并写入到nfs服务器对应的目录中。 2.一个大压缩包下有20多个压缩包,递归解压。解压完成后应该是20多个文件夹,文件夹下有.json文件。 3.pod中的程序解压后去找以.j…...
linux下Qt程序部署教程
文章目录 [toc]1、概述2、静态编译安装Qt1.1 安装依赖1.2 静态编译1.3 报错1.4 添加环境变量1.5 下载安装QtCreator 3、配置linuxdeployqt环境1.1 在线安装依赖1.2 使用linuxdeployqt提供的程序1.3 编译安装linuxdeployqt 4、使用linuxdeployqt打包依赖1.1 linuxdeployqt使用选…...
tp6 合成两个pdf文件(附加pdf或者替换pdf)
最近在做项目有个需求,项目中需要根据设置的html合同模板自动生成PDF合同供客户下载签署,并根据回传的已签署合同尾页来替换原来未签署合同的尾页,合成新的已签署合同文本。 读取两个PDF文件并合成的 具体代码记录如下: use set…...
工作:三菱PLC防止程序存储器爆满方法
工作:三菱PLC防止程序存储器爆满方法 一、防止程序存储器爆满方法1、编程时,添加行注释时,记得要选“外围”,这样不会占用PLC程序存储器内存;2、选择“外围”的注释,前面会有个*星号,方便检查 二…...
jmeter 获取唯一全局变量及多线程读写的问题
一、jmeter 获取唯一ID号全局变量 在JMeter中获取唯一ID号并设置为全局变量,可以通过以下几种方法实现: 使用JMeter内置的UUID函数: JMeter提供了一个内置的函数__UUID,可以生成一个随机的UUID,这个UUID是全局唯一的。…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
