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

P3916 图的遍历(Tarjan缩点和反向建边）

news 来源：原创 2025/5/14 19:24:00

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

编程日记 2025/5/14 19:24:00

Element UI 的 el-tree 组件e中默认展开前两层，设置 default-expanded-keys 属性来实现

在使用 Element UI 的 el-tree 组件时，如果你希望默认展开树的前两层节点，可以通过设置 default-expanded-keys 属性来实现。这个属性接受一个数组，数组中的值是需要默认展开的节点的 key。首先，你需要确保你的每个树节点都有唯…...

编程日记 2025/5/14 19:17:58

Vue 项目中未登录状态如何统一处理

在 Vue 项目中，处理未登录状态（比如用户访问需要登录的页面时）是一项常见的需求。为了实现这一需求，我们通常使用 Vue Router 配合 Vuex 或者 Vue 的全局状态管理来统一处理未登录的状态，确保用户只能访问允许的页面。…...

编程日记 2025/5/14 18:44:31

Java 集合：强大的数据管理工具

在 Java 编程中，集合是一种非常重要的工具，它提供了一种方便的方式来存储和操作一组对象。本文将深入探讨 Java 集合框架，包括其主要类型、特点、用法以及一些最佳实践。一、引言在软件开发过程中，我们经常需要处理一组数据。…...

编程日记 2025/5/14 18:34:43

Creating Server TCP listening socket *:6379: bind: No error

启动redis报错：Creating Server TCP listening socket *:6379: bind: No error 解决方案： 1、直接在命令行中输入 redis-cli.exe 2、输入shutdown，关闭 3、输exit，退出 4、重新输入 redis-server.exe redis.windows.conf&…...

编程日记 2025/5/14 18:28:13

iOS免费共享企业证书、苹果最新企业证书免费获取

前言大家可能都注意到了，苹果手机和安卓手机在安装软件上有点不一样。如果你在苹果手机上想装那些没在官方商店（App Store）里的软件，那就得给它们“签个名”，就像是给它们盖个章，这样手机才能认识它们&am…...

编程日记 2025/5/6 10:02:42

如果用Python写爬虫，具体怎么实现随机请求间隔呢？

在Python中实现随机请求间隔，通常使用time.sleep()函数结合random模块来生成随机的等待时间。以下是一个具体的实现方法： 导入必要的模块首先，你需要导入time和random模块： import time import random 设置随机间隔然后&am…...

编程日记 2025/5/9 14:03:54

aws(学习笔记第十五课) 如何从灾难中恢复（recover）

aws(学习笔记第十五课) 如何从灾难中恢复学习内容： 使用CloudWatch对服务器进行监视与恢复区域(region)，可用区(available zone)和子网(subnet)使用自动扩展(AutoScalingGroup) 1. 使用CloudWatch对服务器进行监视与恢复整体架构这里模拟Jenkins Se…...

编程日记 2025/5/13 11:40:59

nginx4层限速

Nginx的功能概述 Nginx是一个高性能的HTTP和反向代理服务器，也可以作为邮件代理服务器等。它主要工作在7层（应用层），但在某些场景下也可以实现部分4层（传输层）的功能。关于4层限速 Nginx自身的限制&#x…...

编程日记 2025/5/14 8:21:08

Spring Cloud Alibaba 之 “Feign多参数构造”

在上一篇文章整合好了Feign，现在来总结以下Feign调用多参数方法的使用。 GET方式： Spring Cloud为Feign支持了Spring Mvc注解的。如果请求的是localhost:8083/test?id1&namecoco,那么如果我们这样写（User实体类有这二个属性&#xff09…...

编程日记 2025/5/14 3:52:30

C#高级教程

目录 C# 特性（Attribute）C# 反射（Reflection）C# 属性（Property）C# 索引器（Indexer）C# 委托（Delegate）C# 事件（Event）C# 集合&#xf…...

编程日记 2025/5/10 5:23:32

c++ 位图和布隆过滤器

位图（bitmap） 定义位图是一种使用位数组存储数据的结构。每一位表示一个状态，通常用于快速判断某个值是否存在，或者用来表示布尔类型的集合。特点节省空间：一个字节可以表示8个状态。高效操作：位操作…...

编程日记 2025/5/13 9:35:17

基于Springboot开发的云野旅游平台

一、功能介绍云野旅游平台包含管理员、用户两个角色以及前后台系统。前台系统功能用户登录成功后，可以进行查看旅游路线、最新线路、旅游资讯、个人中心、后台管理、购物车、客服等功能模块。进行相对应操作。后台系统功能管理员或用户登录成功后&#xf…...

编程日记 2025/5/14 18:21:53

微服务即时通讯系统（5）用户管理子服务，网关子服务

用户管理子服务（user文件） 用户管理子服务也是这个项目中的一个业务最多的子服务，接口多，但是主要涉及的数据表只有user表，Redis的键值对和ES的一个搜索引擎，主要功能是对用户的个人信息进行修改管理&#…...

编程日记 2025/5/13 2:28:11

docker pull的时候会超时： Error response from daemon: Get "https://registry-1.docker.io/v2/": net/http: request canceled while waiting for connection (Client.Timeout exceeded while awaiting headers) 这时可以找一些代理网站，比如…...

编程日记 2025/5/14 18:59:31

【测试工具JMeter篇】JMeter性能测试入门级教程（四）：JMeter中BeanShell内置方法使用

一、什么是BeanShell BeanShell是一种完全符合Java语法规范的脚本语言,并且又拥有自己的一些语法和方法;BeanShell是一种松散类型的脚本语言(这点和JS类似);BeanShell是用Java写成的,一个小型的、免费的、可以下载的、嵌入式的Java源代码解释器,具有对象脚本语言特性,非常精简…...

编程日记 2025/5/14 19:22:56

JavaScript 键盘控制移动

如果你想通过 JavaScript 实现键盘控制对象（比如一个方块）的移动，下面是一个简单的示例，展示如何监听键盘事件并根据按下的键来移动一个元素。 HTML 和 CSS： <!DOCTYPE html> <html lang"en">…...

编程日记 2025/5/13 23:05:31

如何预防服务器后台爆破攻击

服务器后台爆破（Brute Force Attack）是一种通过反复尝试用户名和密码组合，以非法获取系统访问权限的攻击方式。这种攻击不仅会消耗服务器资源，还可能导致合法用户被锁定或敏感数据泄露。为了有效预防服务器后台爆破攻击&#xff0…...

编程日记 2025/5/14 18:14:05

AI 写作（一）：开启创作新纪元（1/10）

一、AI 写作：重塑创作格局在当今数字化高速发展的时代，AI 写作正以惊人的速度重塑着创作格局。AI 写作在现代社会中占据着举足轻重的地位，发挥着不可替代的作用。随着信息的爆炸式增长，人们对于内容的需求日益旺盛。AI 写作能够…...

编程日记 2025/5/14 11:53:19

【HarmonyOS】鸿蒙应用使用lottie动画

【HarmonyOS】鸿蒙应用使用lottie动画一、lottie动画是什么？ https://airbnb.design/lottie Lottie是由Airbnb团队开发的一个适用于iOS、Android、React Native、Web和Windows的开源动画库，用于解析使用Bodymovin导出为JSON的Adobe After Effects动…...

编程日记 2025/5/12 17:31:17

SQL面试题——腾讯SQL面试题合并连续支付订单

合并连续支付订单现有一张用户支付表：user_pay包含字段订单ID,用户ID,商户ID,支付时间,支付金额。如果同一用户在同一商户存在多笔订单，且中间该用户没有其他商户的支付记录，则认为是连续订单，请把连续订单进行合并，时间取最早支付时间，金额求和。 +----------+------…...

编程日记 2025/5/14 18:24:38

【docker】10. 容器操作案例

容器操作案例容器基本操作 • 通过 nginx 镜像文件创建容器 • 容器的列举(包含正在运行的容器) # 发现此时 e7c33d9f5c61 这个容器运行的状态为 Up,即运行状态 rootLAPTOP-H2EI4I6A:~# docker container ls CONTAINER ID IMAGE COMMAND CREATED …...

编程日记 2025/5/14 19:12:28

postman测试

当然，以下是针对你提供的API层和Service层代码中涉及到的各个接口，如何使用 Postman 进行详细测试的指南。这个指南将帮助你理解如何配置 Postman 来测试这些接口，包括请求的构造、认证的处理、以及如何解读响应。目录准备工作接口测试指…...

编程日记 2025/5/14 19:22:57

【攻防实验】溯源与取证分析实验

溯源与取证分析实验溯源取证分析作为网络攻防过程中重要环节，准确找到攻击者的入侵线索(尤其是攻击突破口、攻击IP地址、域名、工具等信息)，对于企业或者团队安全运营团队来说都是必备技能。常规攻击取证过程中往往会结合流量、Web访问日志、终端系统或…...

编程日记 2025/5/14 19:01:49

【测试工具JMeter篇】JMeter性能测试入门级教程（七）：JMeter断言

一、前言在 JMeter 中，断言元件（Assertion）用于验证测试结果是否符合预期。断言元件可以检查服务器的响应数据，以确保它们符合期望的模式或值，从而验证性能测试脚本的正确性。断言元件通常在每个请求的响应中添加&am…...

编程日记 2025/5/14 18:39:33

Linux 常用命令

目录一、ls 指令二、pwd命令三、cd 指令 1、cd 目录名 2、cd .. 返回上级目录 3、cd ~ 进入用户家目 4、cd - 返回最近访问目录 5、cd相对路径&&cd绝对路径四、touch指令五、mkdir指令 1、mkdir 目录名创建一个目录 2、mkdir -p 递归创建多…...

编程日记 2025/5/14 18:16:16

汽车IVI中控OS Linux driver开发实操（二十八）：回声消除echo cancellation和噪声消除Noise reduction

概述：在当今高度互联的世界中，清晰的实时通信比以往任何时候都更重要。在远程团队会议期间，没有什么能像回声一样打断对话。当说话者听到他们的声音回响时，可能会分散注意力，甚至无法理解对话。即使是很小的回声也会产生很大的影响，仅仅25毫秒的振幅就足以造成声音干扰…...

编程日记 2025/5/10 14:31:56

003-SpringBoot整合Pagehelper

SpringBoot整合Pagehelper 一、引入依赖二、配置 application.yml三、配置 MybatisPlusConfig四、Controller五、ServiceImpl 一、引入依赖 <dependency><groupId>com.github.pagehelper</groupId><artifactId>pagehelper-spring-boot-starter</ar…...

编程日记 2025/5/14 12:40:46

零基础学安全--shell练习

目录用shell写一个计算器测试一些小问题 n阶乘数测试拓展写⼀个Shell脚本去筛选出eth0⽹卡的ipv4地址，并赋值⼀个变量输出测试无限重启用shell写一个计算器 read -p "请输入数字a: " number1 read -p "请输入操作符&#xf…...

编程日记 2025/5/14 3:51:32

【专题】计算机网络之运输层（传输层）

1. 运输层协议概述 1.1 进程之间的通信 (1) 运输层的作用运输层提供进程间的逻辑通信。运输层的屏蔽作用： 运输层向高层用户屏蔽了下面网络核心的细节（如网络拓扑、所采用的路由选择协议等），使应用进程看见的就是好像在两个运…...

编程日记 2025/5/5 13:31:58

【leetcode100】旋转图像

1、题目描述给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例 1： 输入：matrix [[1,2,3],[4,5,6],…...

编程日记 2025/5/14 18:49:19

软件工程——期末复习（1）

名词解释： 名词解释--人月答案：人月是软件开发工作量的单位，1人月表示1个程序员1个月的工作时间所开发的代码量。请解释软件缺陷、错误和失败，并简单举例说明。答案：缺陷（defect）指系统代…...

编程日记 2025/5/14 18:26:55

HTML5系列（3）--多媒体标签详解

前端技术探索系列：HTML5 多媒体标签详解 🎥 开篇寄语 👋 前端开发者们， 在前三篇文章中，我们探讨了 HTML5 的语义化和表单特性。今天，让我们深入了解 HTML5 的多媒体能力，看看如何构建强大的…...

编程日记 2025/5/14 6:38:18

Spring Boot 3.4.0 发布：功能概览与示例

Spring Boot 3.4.0 带来了许多增强功能，使现代应用开发更加高效、便捷和强大。以下是最新功能的完整概述，以及一些帮助您快速入门的代码示例。 1. 应用程序版本管理 Spring Boot 引入了 spring.application.version 属性，方便开发者设置和访…...

编程日记 2025/5/14 19:12:28

【Vue3】【Naive UI】＜n-upload＞标签

【Vue3】【Naive UI】标签基本设置【VUE3】【Naive UI】＜NCard＞ 标签【VUE3】【Naive UI】＜n-button＞ 标签【VUE3】【Naive UI】＜a＞ 标签【VUE3】【Naive UI】＜NDropdown＞ 标签…...

编程日记 2025/5/14 18:12:58

7.代理模式（Proxy Pattern）

古朗月行代理模式JDK动态代理代码示例原码分析 cglib动态代理代码示例源码分析 JDK cglib动态代理对比ClassLoader类的生命周期： 参考资料唐李白小时不识月，呼作白玉盘。又疑瑶台镜，飞在青云端。仙人垂两足，桂树何团团。…...

编程日记 2025/5/6 1:30:22

【效果】回到顶部功能实现

实现效果： 相关代码： <template><div class"cats" :style"{ top: catsTop }" ref"cats" click"catTop"></div> </template> 样式： /* 回到顶部 - 小猫咪 */ .cats {posi…...

编程日记 2025/5/14 0:07:45

项目搭建+修改

一 : 在列表成功回调函数,追加数据中,添加修改的按钮 for (let x of res) {//追加数据$("#table").append(<tr><td><input type"checkbox" class"ck" value"\${x.uid}"></td><td>\${x.uid}</td>…...

编程日记 2025/5/14 18:26:55

GD库如何根据颜色生成纯色背景图

GD库是一个用于图像处理的PHP扩展模块，它提供了一系列函数来创建、编辑和操作图像。要使用GD库根据颜色生成纯色背景图，可以按照以下步骤进行： 一、检查并安装GD库检查GD库是否已安装： 可以通过运行phpinfo();或在命令行中使用p…...

编程日记 2025/5/14 0:07:36

Python 网络爬虫入门全知道

一、引言在当今数字化时代，网络上的数据量呈爆炸式增长。无论是进行数据分析、市场调研，还是开发智能应用，获取网络数据都变得极为重要。而 Python 网络爬虫就是一把打开网络数据宝库的利器。它能够自动地从网页中抓取我们需要的信息&#…...

编程日记 2025/5/11 5:30:30

MATLAB期末复习笔记（下）

目录五、数据和函数的可视化 1.MATLAB的可视化对象 2.二维图形的绘制 3.图形标识 4.多子图绘图 5.直方图的绘制 （1）分类 （2）垂直累计式 （3）垂直分组式 （4）水平分组式 &…...

编程日记 2025/5/14 18:35:58

基于大数据爬虫数据挖掘技术+Python的网络用户购物行为分析与可视化平台(源码+论文+PPT+部署文档教程等)

#1024程序员节｜征文# 博主介绍：CSDN毕设辅导第一人、全网粉丝50W,csdn特邀作者、博客专家、腾讯云社区合作讲师、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老…...

编程日记 2025/5/12 4:34:54

【go】只读通道和只写通道

文章目录概述1. 通道的方向2. 为什么会有只读通道和只写通道？3. 总结概述在 Go 中，只读通道和只写通道的概念通过通道的方向来实现。Go 语言允许你在函数参数中指定通道的方向，从而限制通道的使用方式，这样可以确保代码的清晰…...

编程日记 2025/5/9 0:27:20

带Burst AOT Settings移植问题

报错 burst问题 Burst AOT Settings 是 Unity 的 Burst Compiler 的一部分，用于预编译程序集（AOT，Ahead-Of-Time Compilation），以便在不支持 JIT（即时编译）的平台上运行，例如 iOS 和…...

编程日记 2025/5/14 15:37:55

Debezium日常分享系列之：Debezium Engine

Debezium日常分享系列之：Debezium Engine 依赖打包项目在代码中输出消息格式消息转换消息转换谓词高级记录使用引擎属性异步引擎属性数据库模式历史属性处理故障 Debezium连接器通常通过部署到Kafka Connect服务来运行，并配置一个或多个连接器来监视上游…...

编程日记 2025/5/8 3:11:39

运行 GreatSQL 时为什么要求关闭透明大页

在大部分运维规范中，一般都会要求在运行 GreatSQL/MySQL 的环境中要关闭透明大页，那么到底什么是透明大页，为什么要关闭，打开有什么风险吗？ 在此之前，我也是有点懵的，本文试着回答这个疑问&…...

编程日记 2025/5/13 5:37:22

【Rive】Rive在Android上的简单应用

1 前言 Rive 是一款强大的矢量图编辑器，可以设计图形、也可以制作动画。Rive 提供了矩形、圆形、三角形、多边形、星形、钢笔、文字等工具来绘制各式各样的矢量图形；提供了平移、旋转、缩放等工具对矢量图形进行各种变换；提供了骨骼、约束、时…...

编程日记 2025/5/10 22:03:55

Base 崛起，SynFutures 或成生态系统中最具潜力应用

10月份的 Unchained Crypto 采访中，Solana 联合创始人 Anatoly 表示，通过观察活跃地址数、TVL、DeFi 版块、Meme 热潮和开发者生态等多个关键指标，察觉到 Base 势头正猛，成为以太坊生态最强劲的 L2。 11月下旬，小狐狸创…...

编程日记 2025/5/12 17:35:32

探索Go语言中的循环双向链表

简介循环双向链表将双向链表的灵活性与循环结构相结合，使得每个节点都有一个指向前一个节点和后一个节点的指针，并且最后一个节点的Next指针指向头节点，形成一个闭环。本文将深入探讨如何在Go语言中实现和操作这种数据结构。循环双向链表…...

编程日记 2025/5/8 23:59:11

Leetcode617.合并二叉树(HOT100)+Leetcode79. 单词搜索(HOT100)

链接代码： class Solution { public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(!root1)return root2;if(!root2)return root1;root1->valroot2->val;root1->left mergeTrees(root1->left,root2->left);root1->right merg…...

编程日记 2025/5/11 22:19:45

相关文章：