当前位置: 首页 > 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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...