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

【图论】拓扑排序

一.定义

 拓扑排序是一种对有向无环图(DAG)进行排序的算法,使得图中的每个顶点在排序中都位于其依赖的顶点之后。它通常用于表示一些任务之间的依赖关系,例如在一个项目中,某些任务必须在其他任务之前完成。

拓扑排序的步骤如下:

  1. 找到入度为0的顶点:入度是指指向某个顶点的边的数量。首先,找到图中入度为0的顶点,它们是没有依赖关系的顶点,可以作为排序的起点。

  2. 将入度为0的顶点移出图:选择一个入度为0的顶点,将其从图中移除,并将与之相邻的顶点的入度减1。

  3. 重复步骤1和步骤2:重复上述步骤,直到所有顶点都被移除。如果图是有向无环图,那么拓扑排序会成功完成。

拓扑排序并不是对所有图都适用,只有在有向无环图中才有意义,因为循环依赖会导致拓扑排序无法进行。

 


二.例题

B3644 【模板】拓扑排序 / 家谱树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

三.思路

找出入度为0的点,即为最小辈分的,输出即可,然后取消它的所有连边。

eg:

 可知2无入度,说明2的辈分最小,输出并删除它的连边,print(2)

 

这时4无入度,print(2,4)

 一直重复,print(2,4,5,3,1)


四.参考代码

#include<bits/stdc++.h>
using namespace std;
vector<int>to[101]; 
int in[101];
queue<int>q;
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;while(scanf("%d",&x) && x!=0){to[i].push_back(x);in[x]++;}}for(int i=1;i<=n;i++){if(!in[i]) q.push(i);}while(!q.empty()){int x=q.front();q.pop();cout<<x<<" ";for(int i=0;i<to[x].size();i++){int y=to[x][i];in[y]--;if(!in[y]) q.push(y);}}return 0;
}

五.拓扑+dp

P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


六.思路

不就是最长路吗?Dijkstra直接秒杀。

但还有什么更快的算法吗?

注意:这是有向无环图(DAG),是不是拓扑排序更快呢?拓扑排序就可以找到图的所有直径,然后DP即可。最后输出dp[n];

状态转移方程为:dp[v]=max(dp[v],dp[u]+w);

若dp[n]<0,那就说明没有边可以到达n点


七.参考代码

#include<bits/stdc++.h>
#define maxn 1505
using namespace std;
int n,m;
vector<int> to[maxn],wt[maxn]; 
int in[maxn],dp[maxn];
queue<int> q;
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);to[u].push_back(v);wt[u].push_back(w);in[v]++; }for(int i=1;i<=n;i++){dp[i]=-1e9;if(in[i]==0) q.push(i) ;}dp[1]=0;while(!q.empty()){int x=q.front(); q.pop();for(int i=0;i<to[x].size();i++){int y=to[x][i],w=wt[x][i];dp[y]=max(dp[y],dp[x]+w);in[y]--;if(!in[y]) q.push(y);}}if(dp[n]<0) cout<<-1;else cout<<dp[n];return 0;
}

相关文章:

【图论】拓扑排序

一.定义 拓扑排序是一种对有向无环图&#xff08;DAG&#xff09;进行排序的算法&#xff0c;使得图中的每个顶点在排序中都位于其依赖的顶点之后。它通常用于表示一些任务之间的依赖关系&#xff0c;例如在一个项目中&#xff0c;某些任务必须在其他任务之前完成。 拓扑排序的…...

自动化备份方案

背景说明 网上有很多教程&#xff0c;写的都是从零搭建一个什么什么&#xff0c;基本上都是从无到有的教程&#xff0c;但是&#xff0c;很少有文章提及搭建好之后如何备份&#xff0c;这次通过请教GitHub Copilot Chat&#xff0c;生成几个备份脚本&#xff0c;以备后用。 注…...

win11出现安全中心空白和IT管理员已限制对此应用的某些区域的访问

问题 windows安全中心服务被禁用 winr 输入services.msc 找到windows安全中心服务查看是否被禁用&#xff0c;改为启动&#xff0c;不可以改动看第三条 打开设置&#xff0c;找到应用—windows安全中心–终止–修复–重置 重启如果还是不行看第四条 家庭版系统需要打开gped…...

github实用指令(实验室打工人入门必备)

​​​​​​​​博主进入实验室啦&#xff0c;作为一只手残党决定在这里分享一些常用的github使用情景和操作指南来解救其他手残党。 内容随着情景增加实时更新。如果只有没几个内容说明场景不多&#xff08;相信对手残党而言是再好不过的消息&#xff09; 情景一&#xff1a…...

6. 激活层

6.1 非线性激活 ① inplace为原地替换&#xff0c;若为True&#xff0c;则变量的值被替换。若为False&#xff0c;则会创建一个新变量&#xff0c;将函数处理后的值赋值给新变量&#xff0c;原始变量的值没有修改。 import torch from torch import nn from torch.nn import …...

AIGC ChatGPT 制作地图可视化分析

地图可视化分析是一种将数据通过地图的形式进行展示的方法,可以让人们更加直观、快速、准确的理解和分析数据。以下是地图可视化分析的一些主要好处: 加强数据理解:地图可视化可以将抽象的数字转化为直观的图形,帮助我们更好地理解复杂的数据集。 揭示地理模式:地理位置是…...

2023-08-24 LeetCode每日一题(统计参与通信的服务器)

2023-08-24每日一题 一、题目编号 1267. 统计参与通信的服务器二、题目链接 点击跳转到题目位置 三、题目描述 这里有一幅服务器分布图&#xff0c;服务器的位置标识在 m * n 的整数矩阵网格 grid 中&#xff0c;1 表示单元格上有服务器&#xff0c;0 表示没有。 如果两台…...

前端实习day35

今天是下早班的一天&#xff0c;下完班直接赶车回广州了&#xff0c;吐槽一下深圳站管理得真得差&#xff0c;候车厅小&#xff0c;人巨多&#xff0c;而且进站口的标识也很少&#xff0c;绕了好久才找到&#xff01;下次再也不去了。 今天是改bug的一天&#xff0c;但是有半天…...

Linux安装jupyter notebook

1. Linux安装jupyter notebook 1.1 生成配置文件 这里在conda环境中安装。 jupyter notebook --generate-config --allow-root上面命令是生成配置文件&#xff0c;并且允许使用root用户运行。配置文件默认生成到~/.jupyter/jupyter_notebook_config.py。 具体解释如下&…...

【猿灰灰赠书活动 - 03期】- 【RHCSA/RHCE 红帽Linux认证学习指南(第7版) EX200 EX300】

说明&#xff1a;博文为大家争取福利&#xff0c;与清华大学出版社合作进行送书活动 图书&#xff1a;《RHCSA/RHCE 红帽Linux认证学习指南(第7版) EX200 & EX300》 一、好书推荐 图书介绍 《RHCSA/RHCE 红帽Linux认证学习指南&#xff08;第7版&#xff09; EX200 & E…...

当 Tubi 遇到 Ruby

有人说 Tubi 作为 RubyConf China 金牌赞助商&#xff0c;明明用极具吸引力的 Elixir 后端工程师岗位和高品质的 Elixir Meetup&#xff0c;“拐走了”一批又一批 Rubyist 投身于 Elixir 开发中&#xff0c;却依然让人想在 Tubi 展台前多停留一会儿。 为什么工程师、校友甚至 …...

【C++从0到王者】第二十四站:多态的底层原理

文章目录 前言一、虚函数表二、一道经典的例题三、深度剖析多态的条件之一&#xff1a;为什么必须是父类的指针或引用四、深度剖析多态的条件之二&#xff1a;为什么是虚函数的重写/覆盖&#xff1f;五、虚函数表的一些总结六、关于Func3的验证七、动态绑定与静态绑定八、总结 …...

Java从入门到精通24==》数据库、SQL基本语句、DDL语句

Java从入门到精通24》数据库、SQL基本语句、DDL语句 2023.8.27 文章目录 <center>Java从入门到精通24》数据库、SQL基本语句、DDL语句一、什么是数据库二、数据库的优缺点1、使用数据库的优点&#xff1a;2、使用数据库的缺点&#xff1a; 三、MySQL基本语句四、DDL语句 …...

学习ts(十)装饰器

定义 装饰器是一种特殊类型的声明&#xff0c;它能够被附加到类声明&#xff0c;方法&#xff0c;访问符&#xff0c;属性或参数上&#xff0c;是一种在不改变原类和使用继承的情况下&#xff0c;动态的扩展对象功能。 装饰器使用expression形式&#xff0c;其中expression必须…...

如何在 Opera 中启用DNS over HTTPS

DNS over HTTPS&#xff08;基于HTTPS的DNS&#xff09;是一种更安全的浏览方式&#xff0c;但大多数 Web 浏览器默认情况下不启用它。了解如何在 Opera 浏览器中启用该功能。 您可能不知道这一点&#xff0c;但您的网络浏览器并不像您希望的那样私密或安全。您会看到&#xff…...

STM32 F103C8T6学习笔记13:IIC通信—AHT10温湿度传感器模块

今日学习一下这款AHT10 温湿度传感器模块&#xff0c;给我的OLED手环添加上测温湿度的功能。 文章提供源码、测试工程下载、测试效果图。 目录 AHT10温湿度传感器&#xff1a; 特性&#xff1a; 连接方式&#xff1a; 适用场所范围&#xff1a; 程序设计&#xff1a; 设…...

QT基础使用:组件和代码关联(信号和槽)

自动关联 ui文件在设计环境下&#xff0c;能看到的组件可以使用鼠标右键选择“转到槽”就是开始组件和动作关联。 在自动关联这个过程中软件自动动作的部分 需要对前面头文件进行保存&#xff0c;才能使得声明的函数能够使用。为了方便&#xff0c;自动关联时先对所有文件…...

TCP最大连接数问题总结

最大TCP连接数量限制有&#xff1a;可用端口号数量、文件描述符数量、线程、内存、CPU等。每个TCP连接都需要以下资源&#xff0c;如图所示&#xff1a; 1、可用端口号限制 Q&#xff1a;一台主机可以有多少端口号&#xff1f;端口号与TCP连接&#xff1f;是否能修改&#x…...

【Docker】云原生利用Docker确保环境安全、部署的安全性、安全问题的主要表现和新兴技术产生

前言 Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux或Windows操作系统的机器上,也可以实现虚拟化,容器是完全使用沙箱机制,相互之间不会有任何接口。 云原生利用Docker确保环境安全、部署的…...

explain各个字段代表的意思

id&#xff1a;联表查询是每个表的读取顺序&#xff0c;数字越大越先被读取。相同就需要通过table字段判断select_type&#xff1a;查询类型或者是其他操作类型&#xff08;PRIMARY、UNION、UNION RESULT等&#xff09;table&#xff1a;正在访问哪个表partitions&#xff1a;匹…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...