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

acwing算法基础之搜索与图论--有向图的拓扑序列

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

拓扑序列:针对有向图而言,该序列内,所有边都是从前指向后的。

如果存在环,那么该图一定不存在拓扑序列。否则,一定存在拓扑序列。

有向图中的入度和出度。
入度为0的结点,可以作为拓扑序列的起点。

求拓扑序列的关键步骤:

  1. 把入度为0的结点插入队列q。
  2. 弹出队头t,遍历队头t的下一个结点,将其入度减1。操作之后,如果其值为0,则插入队列q。
  3. 重复进行步骤2,直至队列q为空。

2 模板

题目1:给出结点数目n和边数m,以及一系列的边,如果此图存在拓扑序列,请输出(输出任意一种拓扑序列即可);否则,输出-1。

#include <iostream>
#include <vector>
#include <queue>using namespace std;const int N = 1e5 + 10;
int n, m;
vector<vector<int>> g(N);
vector<int> d(N); //存储每个结点的入度int main() {cin >> n >> m;int x, y;while (m--) {cin >> x >> y;//添加x到y的边g[x].emplace_back(y);d[y]++;}queue<int> q;for (int i = 1; i <= n; ++i) {if (d[i] == 0) {q.push(i);}}vector<int> res;while (!q.empty()) {auto t = q.front();res.emplace_back(t); //存入向量res中 q.pop();//t可以走到哪里for (auto x : g[t]) {//把结点t删除d[x]--;if (d[x] == 0) {q.push(x);}}}if (res.size() == n) {for (int i = 0; i < n; ++i) cout << res[i] << ' ';cout << endl;} else {puts("-1");}return 0;
}

3 工程化

暂无。。。

相关文章:

acwing算法基础之搜索与图论--有向图的拓扑序列

目录 1 基础知识2 模板3 工程化 1 基础知识 拓扑序列&#xff1a;针对有向图而言&#xff0c;该序列内&#xff0c;所有边都是从前指向后的。 如果存在环&#xff0c;那么该图一定不存在拓扑序列。否则&#xff0c;一定存在拓扑序列。 有向图中的入度和出度。 入度为0的结点…...

Unity之NetCode多人网络游戏联机对战教程(7)--联机概念理解权威性Authority

文章目录 前言IsOwner权威 / AuthoritativeIsHostIsServerIsClientIsLocalPlayer 前言 在联机游戏中&#xff0c;常见的模式有Peer-to-Peer, Client与Server&#xff0c;也就是CS架构。NetCode基于CS架构开发&#xff0c;下面讲解一些概念知识。在NetCode中&#xff0c;会涉及…...

Go并发编程(上)

目录 一、go语言当中的协程 二、MPG模型介绍 三、Goroutine 的使用 3.1 协程的开启 3.2 优雅地等待子协程结束 四、捕获子协程的panic 五、管道Channel 5.1、认识管道 5.2、Channel的遍历和关闭 5.3 、用管道实现生产者消费者模型 5.4、Channel一些使用细节和注意事…...

MarkDown基础及表格、KaTeX公式、矩阵、流程图、UML图、甘特图语法

概述 最多可设置6级标题 技巧 列表 有序列表 MD语法&#xff1a; 1. 你好 2. 我也好呈现效果&#xff1a; 你好我也好 无序列表 MD语法&#xff1a; - a - b * aa * bbaaabbb效果&#xff1a; ab aabb aaabbb 结论&#xff0c;支持三种方式&#xff1a;-、*、 T…...

Citespace的使用

CiteSpace CiteSpace的相关介绍运行CiteSpace CiteSpace的相关介绍 CiteSpace作为一款优秀的文献计量学软件&#xff0c;能够将文献之间的关系以科学知识图谱的方式可视化地展现在我们面前。简单来说&#xff0c;面对海量的文献&#xff0c;CiteSpace能够迅速锁定自己需要关注…...

[模块]ES6与cjs的混合开发

[模块]ES6与cjs的混合开发 模块语言混合开发的原因Nodejs中使用ES6关于动态加载的讲解 项目的模块语言CJS 与 ESM 开发模块的使用方法普通模块引入json 文件的引入普通模块导出 CJS兼容ESMESM兼容CJS(推荐)全局变量--dirname-filename-esm库 问题Error: EPERM: operation not p…...

git上传项目至github(Linux)

01 git版本创建 git init 创建版本库 创建一个版本 git add test1.cpp git commit -m 说明信息 git log 查看版本记录 02 版本回退 git reset --hard HEAD^ 版本回退一个 git reset --hard HEAD^^ 版本回退二个 git reset --hard 版本号 版本回退到指定版本&#xff0…...

SSH 远程登录 WSL

更新ssh设置 sudo apt-get update sudo apt-get remove openssh-server sudo apt-get install openssh-server 编辑网络配置 sudo vi /etc/ssh/sshd_config &#xff08;1&#xff09;修改ssh服务监听端口和监听地址 注意&#xff1a;为了个人的安全&#xff0c;还是建议换…...

每天一道算法题:40. 组合总和 II

难度 中等 题目 给定一个候选人编号的集合 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意&#xff1a;解集不能包含重复的组合。 示例 1: 输入: candidat…...

Centos7安装PostgreSQL 14

环境&#xff1a; Centos7安装PostgreSQL_14版本数据库&#xff1b; 打开官方网站&#xff1a;PostgreSQL: Linux downloads (Red Hat family) 一、 版本选择 复制、粘贴并运行如下脚本&#xff1a; 二、安装步骤 这些命令是在 CentOS 7.x 系统上安装和配置 PostgreSQL 14 的步…...

Shopee的折扣活动怎么分类?shopee设置折扣注意事项

旺季到来&#xff0c;Shopee会举办一些折扣活动来吸引客户&#xff0c;那么shopee的折扣活动怎么分类&#xff0c;shopee设置折扣注意事项&#xff1f; shopee的折扣活动怎么分类&#xff1f; 满减活动&#xff1a;满减活动是虾皮常见的一种折扣形式。在这种活动中&#xff0…...

磁盘空间占用巨大的meta.db-wal文件缓存(tracker-miner-fs索引服务)彻底清除办法

磁盘命令参考本博客linux磁盘空间满了怎么办. 问题: 磁盘空间被盗 今天瞄了一下我的Ubuntu系统盘&#xff0c; nftdiggernftdigger-Ubuntu:~$ df -h 文件系统 容量 已用 可用 已用% 挂载点 udev 16G 0 16G 0% /dev tmpfs 3.2G 1.9…...

力扣:160. 相交链表(Python3)

题目&#xff1a; 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;…...

【华为OD机试AB高分必刷题目】无名的搜索题(Java-优先搜索(DFS)实现)

🚀你的旅程将在这里启航!本专栏所有题目均包含优质解题思路,高质量解题代码,详细代码讲解,助你深入学习,高分通过! 文章目录 【华为OD机试AB高分必刷题目】无名的搜索题(Java-优先搜索(DFS)实现)题目描述解题思路Java题解代码代码OJ评判结果代码讲解寄语【华为OD机…...

ant 任务(task)通过内嵌的arg元素传递命令行参数

有的ant 任务将参数传递给其它的进程作为命令行参数。这可以通过内嵌的arg元素来实现。 例如&#xff1a; <exec executable"${browser}" spawn"true"><arg value"${file}"/> </exec>arg元素的部分属性说明&#xff1a; val…...

STM32G0+EMW3080+阿里云飞燕平台实现单片机WiFi智能联网功能(三)STM32G0控制EMW3080实现IoT功能

项目描述&#xff1a;该系列记录了STM32G0EMW3080实现单片机智能联网功能项目的从零开始一步步的实现过程&#xff1b;硬件环境&#xff1a;单片机为STM32G030C8T6&#xff1b;物联网模块为EMW3080V2-P&#xff1b;网联网模块的开发板为MXKit开发套件&#xff0c;具体型号为XCH…...

IntelliJ IDEA - Git Commit 后 Commit 窗口不消失解决方案

这个现象是在 2023 年版本后开始的&#xff0c;一开始以为是 Mac 系统的原因&#xff0c;后来发现原来 Windows 也这样&#xff0c;所以应该只跟 IDEA 版本有关 可以看到左侧 commit 后&#xff0c;这个侧边栏还在&#xff0c;按理讲在以前的版本是之前消失&#xff0c;这样使…...

Vue 组件化编程 和 生命周期

目录 一、组件化编程 1.基本介绍 : 2.原理示意图 : 3.全局组件示例 : 4.局部组件示例 : 5.全局组件和局部组件的区别 : 二、生命周期 1.基本介绍 : 2.生命周期示意图 : 3.实例测试 : 一、组件化编程 1.基本介绍 : (1) 开发大型应用的时候&#xff0c;页面往往划分成…...

《数字图像处理-OpenCV/Python》连载(41)图像的旋转

《数字图像处理-OpenCV/Python》连载&#xff08;41&#xff09;图像的旋转 本书京东优惠购书链接&#xff1a;https://item.jd.com/14098452.html 本书CSDN独家连载专栏&#xff1a;https://blog.csdn.net/youcans/category_12418787.html 第 6 章 图像的几何变换 几何变换分…...

案例 - 拖拽上传文件,生成缩略图

直接看效果 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>拖拽上传文件</title>&l…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

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

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

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...