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

搜索与图论-拓扑序列

为什么记录呢
因为不记录全忘了
虽然记了也不一定会看

  1. 有向无环图一定有拓扑序列
  2. 邮箱无环图 - 拓扑图
  1. 入度为0的点作为起点
  2. 入度为0的点入队列
  3. 枚举出边 t->j
  4. 删掉当前边,t->j . j的入度减1
  5. 判断j的入度是否为0,来判断是否加入队列
  1. 有环: 不存在入度为0的点
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>using namespace std;const int maxn = 100010;int h[maxn], e[maxn], ne[maxn], idx;int q[maxn],d[maxn];int n;int hh = 0, tt = -1;void add(int a, int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}bool topsort(){while(hh <= tt){int t = q[hh++];for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];d[j]--;if(d[j] == 0){q[++tt] = j;// cout<<"j: "<< j << " "; }}}// cout<<"tt " << tt << "n-1 "<< n-1 << '\n';return tt == n-1;}int main(){int m,a,b;memset(h , -1, sizeof h);cin >> n >> m;for(int i = 0; i < m; i++){cin>>a>>b;add(a,b);// cout<<"b  "<< b << " ";d[b]++;}for(int i = 1; i <= n; i++){if(d[i] == 0){// cout<<"i: " << i<<'\n';q[++tt] = i;}}if(topsort()){for(int i = 0; i < n; i++){cout<<q[i] << " ";}}else cout<<-1<< '\n';return 0;
}

相关文章:

搜索与图论-拓扑序列

为什么记录呢 因为不记录全忘了 虽然记了也不一定会看 有向无环图一定有拓扑序列邮箱无环图 - 拓扑图 入度为0的点作为起点入度为0的点入队列枚举出边 t->j删掉当前边&#xff0c;t->j . j的入度减1判断j的入度是否为0&#xff0c;来判断是否加入队列 有环&#xff1a; …...

「MySQL-05」MySQL Workbench的下载和使用

目录 一、MySQL workbench的下载和安装 1. MySQL workbench介绍 2. 到MySQL官网下载mysql workbench 3. 安装workbench 二、创建能远程登录的用户并授权 1. 创建用户oj_client 2. 创建oj数据库 3. 给用户授权 4. 在Linux上登录用户oj_client检查其是否能操作oj数据库 三、使用…...

编译期jni类型转换成字符串

背景: 例如android jni 方法的签名, 这个需要每个用户都要知道具体类型,转化成签名, 要想写好签名, 必须很熟悉 类型对应的签名, 尤其java类对象要加个L, 本文将介绍怎么在编译期过程把类型转化成字符, 多个类型在尽性拼接. 定义基础数据结构 template<char ... ch> str…...

优秀的ui设计作品(合集)

UI设计师需要了解的九个Tips 1.图片类APP排版突破 规则是死的&#xff0c;人是活的。很多时候&#xff0c;如果需求是比较宽要尝试突破原则&#xff0c;用一些另类的排版方式&#xff0c;其实也是做好设计的本质。在图片类app中&#xff0c;错落一些的排版会使你的作品更有魅力…...

【c/c++】c和cpp混合编译

c和cpp混合编译 #ifdef __cplusplus extern "C" { #endifextern int test(int, int);#ifdef __cplusplus } #endif在这段代码中&#xff0c;#ifdef __cplusplus 和 #endif 之间的代码是为了在 C 中使用 C 语言的函数声明和定义时&#xff0c;确保编译器正确地处理 C…...

springboot定制banner

这里有几个定制banner的网站 Text to ASCII Art Generator (TAAG) ASCII Generator IMG2TXT: ASCII Art Made Easy!...

Qt 入门实战教程(目录)

为何我要写Qt入门教程 前置课程 《C自学精简实践教程》 教程特点 1 面向企业开发&#xff0c;你在这里学到的任何一步操作&#xff0c;都会直接在企业里用到。 2 注重设计思路训练&#xff0c;抽象分析问题的能力。 Qt 安装 1.1 Windows Qt 5.12.10下载与安装 1.2 我们…...

Ceph入门到精通-Lunix性能分析工具汇总

出于对Linux操作系统的兴趣&#xff0c;以及对底层知识的强烈欲望&#xff0c;因此整理了这篇文章。本文也可以作为检验基础知识的指标&#xff0c;另外文章涵盖了一个系统的方方面面。如果没有完善的计算机系统知识&#xff0c;网络知识和操作系统知识&#xff0c;文档中的工具…...

服务器端使用django websocket,客户端使用uniapp 请问服务端和客户端群组互发消息的代码怎么写的参考笔记

2023/8/29 19:21:11 服务器端使用django websocket,客户端使用uniapp 请问服务端和客户端群组互发消息的代码怎么写 2023/8/29 19:22:25 在服务器端使用Django WebSocket和客户端使用Uniapp的情况下&#xff0c;以下是代码示例来实现服务器端和客户端之间的群组互发消息。 …...

【考研数学】线性代数第四章 —— 线性方程组(2,线性方程组的通解 | 理论延伸)

文章目录 引言四、线性方程组的通解4.1 齐次线性方程组4.2 非齐次线性方程组 五、方程组解的理论延伸 引言 承接前文&#xff0c;继续学习线性方程组的内容&#xff0c;从方程组的通解开始。 四、线性方程组的通解 4.1 齐次线性方程组 &#xff08;1&#xff09;基础解系 —…...

go读取文件的几种方法

一. 整个文件读入内存 直接将数据直接读取入内存&#xff0c;是效率最高的一种方式&#xff0c;但此种方式&#xff0c;仅适用于小文件&#xff0c;对于大文件&#xff0c;则不适合&#xff0c;因为比较浪费内存 1.直接指定文化名读取 在 Go 1.16 开始&#xff0c;ioutil.Rea…...

ChatGPT癌症治疗“困难重重”,真假混讲难辨真假,准确有待提高

近年来&#xff0c;人工智能在医疗领域的应用逐渐增多&#xff0c;其中自然语言处理模型如ChatGPT在提供医疗建议和信息方面引起了广泛关注。然而&#xff0c;最新的研究表明&#xff0c;尽管ChatGPT在许多领域取得了成功&#xff0c;但它在癌症治疗方案上的准确性仍有待提高。…...

docker打包vue vite前端项目

打包vue vite 前端项目 1.打包时将测试删除 2.修改配置 3.打包项目 npm run build 显示成功&#xff08;黄的也不知道是啥&#xff09; 打包好的前端文件放入 4.配置 default.conf upstream wms-app {server 你自己的ip加端口 ;server 192.168.xx.xx:8080 ; } server { …...

zookeeper 查询注册的 dubbo 服务

1. 连接zookeeper 服务端 使用bin 目录下zk客户端连接服务器&#xff0c; ./zkCli.sh -server 127.0.0.1:2181 2. 查询Dubbo 服务 # 查询所有服务 ls /dubbo # 查询指定服务调用 ls /dubbo/服务名(接口地址)/consumers # 查询指定服务调用 ls /dubbo/服务名(接口地址)/pr…...

【每日一题】57. 插入区间

【每日一题】57. 插入区间 57. 插入区间题目描述解题思路 57. 插入区间 题目描述 给你一个 无重叠的 &#xff0c;按照区间起始端点排序的区间列表。 在列表中插入一个新的区间&#xff0c;你需要确保列表中的区间仍然有序且不重叠&#xff08;如果有必要的话&#xff0c;可…...

youtubu视频下载和yt-dlp 使用教程

参考&#xff1a;https://zhuanlan.zhihu.com/p/618467617&#xff0c;使用 yt-dlp 下载 youtube 视频的一点体会 安装yt-dlp 1. 安装Python和ffmpeg Python&#xff1a;安装时把pip和添加系统环境变量都选上 ffmpeg&#xff1a;下载好exe文件&#xff0c;把目录添加到系统环…...

——滑动窗口

滑动窗口 所谓滑动窗口&#xff0c;就是不断的调节子序列的起始位置和终止位置&#xff0c;从而得出我们要想的结果。也可以理解为一种双指针的做法。 leetcode76 class Solution {public String minWindow(String s, String t) {char[] schars s.toCharArray();char[] tc…...

【C++进阶】模板进阶

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前学习C和算法 ✈️专栏&#xff1a;C航路 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点赞&#x1…...

Vim如何清空文件

在Vim中&#xff0c;可以使用以下命令清空文件内容&#xff1a; 打开需要清空的文件&#xff1a;在终端中输入vim filename打开文件&#xff0c;其中filename是你要编辑的文件名。 进入命令模式&#xff1a;按下键盘上的Esc键&#xff0c;确保处于Vim的命令模式。&#xff08;…...

问道管理:什么信号?煤飞色舞钢花溅

近期重磅利好不断&#xff0c;对应到A股商场&#xff0c;究竟哪个板块最获益&#xff0c;商场讨论热烈。 地产分析师&#xff1a;方针力度超预期&#xff0c;主张加仓。 银行分析师&#xff1a;存量房贷对银行股心情上的压制完毕&#xff0c;值得重视。 消费分析师&#xff…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...