数据分析
1024程序员节
utf8
CTF
arm开发
design_pattern
nginx
开发板
小目标
Nacos
Hash
gaussdb
统一认证
时间尺度
湖南大学
死锁
研发效能
飞书
学生网页作业
dp
拓扑排序
2024/4/12 2:07:40
HDU 4857 逃生 （逆向拓扑排序、优先队列）
传送门：HDU 4857题目给的输入输出数据不够典型，下面给出我自己的数据：Sample Input17 66 15 24 31 72 73 7Sample Output6 1 5 2 4 3 7题目大意：
中文题，就不解释了。有题意可以知道，可能存在多种结果&…
【LeetCode: 210. 课程表 II:拓扑排序+图】
🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…
拓扑排序-HDU1285( 确定比赛名次 )
点击打开题目链接
又是一道拓扑排序模板题，和POJ2637几乎一模一样的。
题意就不用说了吧，就是中文题目要求什么也很清楚。这里要说一下，这道题除了要求输出拓扑排序后的顺序，还额外要求在符合题目条件的情况下，输出编号…
洛谷——P1347 排序（图论-拓扑排序）
文章目录 一、题目排序题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示 二、题解基本思路：代码 一、题目
排序
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的…
拓扑排序模板题-POJ 2367(Genealogical tree )
点击打开题目链接
本题是拓扑排序的模板题，如果还不知道什么是拓扑排序的同学，可以参看这位大神博客里面的手动模拟拓扑排序的过程，相信看完以后你就会懂了什么是拓扑排序了。（链接：https://blog.csdn.net/qq_35644234…
【LeetCode】210. 课程表 II——拓扑排序
题目链接：210. 课程表 II 题目描述： 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如…
LeetCode 1462. 课程表 IV：拓扑排序
【LetMeFly】1462.课程表 IV：拓扑排序
力扣题目链接：https://leetcode.cn/problems/course-schedule-iv/
你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisite…
1462. 课程表 IV
文章目录 Tag题目来源题目解读解题思路方法一：Floyd传递闭包方法二：拓扑排序 思考写在最后 Tag
【拓扑排序】【传递闭包】【并查集】【数组】 题目来源
1462. 课程表 IV 题目解读
给你一个表示课程先决条件的数组 prerequisites，prerequis…
C++ 图系列之基于有向无环图的拓扑排序算法
1. 前言
有向无环图，字面而言，指图中不存在环(回路)，意味着从任一顶点出发都不可能回到顶点本身。有向无环图也称为 DAG（Directed Acycline Graph）。
有向无环图可用来描述顶点之间的依赖关系，依赖这个概…
Java高阶数据结构 图补充-拓扑排序
拓扑排序 文章目录 Java高阶数据结构 & 图补充-拓扑排序1. 什么是拓扑排序2. 拓扑排序算法思想-卡恩算法3. 拓扑排序代码实现3.1 遍历链表计算入度3.2 挑选一个入度为0的顶点3.3 输出顶点3.4 判断循环结束是否为全-13.4 *kahn*方法3.5 测试 Java高阶数据结构 & 图补充…
Leetcode210. 课程表 II
Every day a Leetcode
题目来源：210. 课程表 II
解法1：
什么是拓扑排序？ 我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我…
【图论】【拓扑排序】1857. 有向图中最大颜色值
本文涉及的知识点
图论 拓扑排序
LeetCode1857. 有向图中最大颜色值
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。 给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 …
【逆向思考 】【拓扑排序】1591. 奇怪的打印机 II
本文涉及的知识点
逆向思考 拓扑排序
LeetCode1591. 奇怪的打印机 II
给你一个奇怪的打印机，它有如下两个特殊的打印规则：
每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。 一…
图算法小结(并查集)
（0）目录
图算法小结(prime与dijkstra对比)
图算法小结(并查集)
哈夫曼树 之 建树和编解码
一：起因
（1）关于图的算法一般是比较复杂的，自己在这方面也是比较弱的，首先是图的存储问题 和 …
1146 Topological Order(31行代码+详细注释)
分数 25
全屏浏览题目
作者 CHEN, Yue
单位 浙江大学
This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test …
LeetCode210. Course Schedule II——拓扑排序
文章目录 一、题目二、题解 一、题目
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] [ai, bi] indicates that you must take course bi first if you want t…
【王道数据结构】【chapter6图】【P258t7】
试编写 利用DFS实现有向无环图的拓扑排序的算法 #include <iostream>
#define maxsize 10
typedef struct node{int data;struct node *next;
}node ,*pnode;pnode buynode(int x)
{pnode tmp(pnode) malloc(sizeof (node));tmp->datax;tmp->next nullptr;return t…
【洛谷】B3644 【模板】拓扑排序 / 家谱树（用邻接表存储和其他题解不一样哦）
本薅蒻通过这次学到的知识点（本人认为好用的东西）： 1： （情况适用于输入的x为0时结束输入）
2： 先输出“t”(就是因为这里wa了好几发，555555)
原本是在 if里面输出的，这…
拓扑排序软件设计——ToplogicalSort_app（含有源码、需求分析、可行性分析、概要设计、用户使用手册）
拓扑排序软件设计 前言1. 需求分析2. 可行性分析2.1 简介2.2 技术可行性分析2.2.1 技术实现方案2.2.2 开发人员技能要求2.2.3 可行性 2.3 操作可行性分析2.4 结论 3. 项目报告3.1 修订历史记录3.2 软硬件环境3.3 需求分析3.4 详细设计3.4.1 类设计3.4.2 核心流程描述3.4.3 核心…
LeetCode 207. Course Schedule
原题目：https://leetcode-cn.com/problems/course-schedule/ 思路：
构建图结构和入度数组。每次遍历入度为0的点，以该点为头结点的边，其尾结点的入度-1.
如果最后入度为0的数和numclass相等，就返回true； …
2022 icpc 西安站 L. Tree - 拓扑排序
题面
分析
题意就是求集合个数，满足集合所有点都是子节点和父节点关系或者不存在祖孙关系。那么可以将树拆分成若干条链，然后每次减少链数，将减少的链转化成另一种情况，也就是枚举所有链数的方案，取最小值。 对于求链…
Codeforces Round 925 (Div. 3)F. Chat Screenshots 拓扑排序
Problem - F - Codeforces
比如 1 2 3 4 5
除去3就是 3 1 2 4 5
本题是给若干个除去某个数外的顺序，让判断这些顺序是否唯一。
这些顺序是确定的，即前后关系定好了，我们可以建有向图，然后拓扑排序。
如果唯一，是可…
OJ练习第166题——课程表（拓扑排序问题）
课程表
力扣链接：207. 课程表
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] [ai, bi] ，表…
![[LeetBook]【学习日记】有效数字——状态机](https://img-blog.csdnimg.cn/direct/20d29e0d3a754a9e910202f39a704469.png)
[LeetBook]【学习日记】有效数字——状态机
题目
有效数字 有效数字（按顺序）可以分成以下几个部分： 若干空格一个小数或者整数（可选）一个’e’或’E’，后面跟着一个整数若干空格 小数（按顺序）可以分成以下几个部分：…
【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠
作者推荐
【动态规划】【map】【C算法】1289. 下降路径最小和 II
本文涉及知识点
广度优先搜索 拓扑排序 逆推
LeetCode913. 猫和老鼠
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。 图的形式是：graph[a] 是一个列…
数据结构--拓扑排序
数据结构–拓扑排序
AOV⽹ A O V ⽹ \color{red}AOV⽹ AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)： ⽤ D A G 图 \color{red}DAG图 DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边 < V i , V j …
数据结构课设——拓扑排序
题目
编写函数实现图的拓扑排序。
代码
#include <bits/stdc.h>
using namespace std;
const int N 1e5 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int vis[N];
void add(int a, int b);
void topsort();
void input();
int main()
{input();topsort();…
有向图中寻找强连通分量（环）和拓扑排序——Kosaraju、Trajan、Gabow算法
最关键通用部分：强连通分量一定是图的深搜树的一个子树。
一、 Kosaraju算法
1. 算法思路
基本思路： 这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。(步骤1)先用对原图G进行深搜形成森…
还不会拓扑排序？看这一篇就够了
目录一、什么是拓扑排序？二、拓扑排序的实现2.1 拓扑排序模版三、拓扑排序的应用3.1 有向图的拓扑序列3.2 家谱树3.3 奖金3.4 可达性统计3.5 Directing Edges一、什么是拓扑排序？
拓扑排序是一种有向无环图（DAG）的顶点排序方法&a…
王道数据结构课代表 - 考研数据结构 第六章 图 究极精华总结笔记
本篇博客是考研期间学习王道课程传送门的笔记，以及一整年里对数据结构知识点的理解的总结。希望对新一届的计算机考研人提供帮助！！！ 关于对 “图” 章节知识点总结的十分全面，涵括了《王道数据结构》课程里的全部要点&…
拓扑排序实现循环依赖判断 | 京东云技术团队
本文记录如何通过拓扑排序，实现循环依赖判断
前言
一般提到循环依赖，首先想到的就是Spring框架提供的Bean的循环依赖检测，相关文档可参考： https://blog.csdn.net/cristianoxm/article/details/113246104 本文方案脱离Spring Be…
poj 1094 拓扑排序
参考了大神的代码。。偶实在太弱了 T_T #include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; const int MAXN 27; int n, m; int G[MAXN][MAXN];//建立两点的出入关系 int in[MAXN];//统计入度 int…
多式联运路径优化问题：基于拓扑排序的遗传算法染色体编码
一、什么是拓扑排序
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
每个顶点出现且只出现一次。若存在一…
【LeetCode每日一题合集】2023.9.18-2023.9.24（⭐拓扑排序⭐设计数据结构:LRU缓存实现 LinkedHashMap⭐）
文章目录 337. 打家劫舍 III（树形DP）2560. 打家劫舍 IV（二分查找动态规划）LCP 06. 拿硬币（简单贪心模拟）2603. 收集树中金币⭐思路——拓扑排序删边 2591. 将钱分给最多的儿童（分类讨论…
【LeetCode: 1462. 课程表 IV:拓扑排序+图+广度优先搜索】
🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…
数据结构：图--拓扑排序
拓扑排序
拓扑排序 在实际应用中，有向图的边可以看做是顶点之间制约关系的描述。把顶点看作是一个个任务，则对于有向边<Vi,Vj>表明任务Vj的启动需等到任务Vi完成之后，也就是说任务Vi先于任务Vj完成。对于一个有向图，找出一…
【LeetCode每日一题合集】2023.9.4-2023.9.10（⭐二叉树的重建二分答案拓扑排序）
文章目录 449. 序列化和反序列化二叉搜索树⭐⭐⭐⭐⭐（二叉树的重建）解法相关题目——297. 二叉树的序列化与反序列化⭐⭐⭐⭐⭐解法——深度优先搜索 2605. 从两个数字数组里生成最小数字哈希表分情况讨论位运算表示集合，分情况讨论…
LeetCode207之课程表(相关话题：图的遍历，拓扑排序)
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 b…
【Leetcode】269.火星词典（Hard）
一、题目
1、题目描述
现有一种使用英语字母的火星语言，这门语言的字母顺序与英语顺序不同。
给你一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序…
拓扑排序的原理与实现
什么是拓扑排序？
拓扑排序顾名思义是一种排序算法，它用于给有向图排序。
有向图是由一组顶点和一组有方向的边组成的图，每条有方向的边都连接着有序的一对顶点，因此A -> B代表A可以到达B，并不代表B就能到达A。
拓扑…
【算法】NOIP2003神经网络
题目描述 人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的…
图的应用3.0-----拓扑排序
目录
前言
AOE网
1.相关概念
2.AOE网特征
拓扑排序
1.基本概念
2.方法步骤 3.拓扑排序的应用
拓扑排序代码实现
1.邻接矩阵的代码
2.邻接表代码 前言 今天我们学习图的应用----拓扑排序，说到排序，你们是不是会想到冒泡排序，插入排序…
第 365 场 LeetCode 周赛题解
A 有序三元组中的最大值 I 参考 B B B 题做法… class Solution {
public:using ll long long;long long maximumTripletValue(vector<int> &nums) {int n nums.size();vector<int> suf(n);partial_sum(nums.rbegin(), nums.rend(), suf.rbegin(), [](int x…
算法导论-上课笔记9:基本的图算法
文章目录0 前言1 图的表示1.1 邻接链表法1.2 邻接矩阵法1.3 表示图的属性2 广度优先搜索2.1 最短路径2.2 广度优先树3 深度优先搜索3.1 深度优先搜索的性质3.2 边的分类4 拓扑排序5 强连通分量0 前言
本文将介绍图的表示和图的搜索。图的搜索指的是系统化地跟随图中的边来访问…
C++解题报告：病毒(virus)——拓扑排序
题目描述
有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。
现在怎么恢复原来的文档呢…
间谍网络（C++，强连通分量，缩点）
题目描述
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以&#x…
C++算法:矩阵中的最长递增路径
涉及知识点
拓扑排序
题目
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允…
PAT备考之 拓扑排序 专题
拓扑排序可以用于有向无环图的判断 下面是我自己比较习惯的写法。
（TIP：如果题目条件中有说，当有多个事件可以进行时，可以使用优先队列
优先进行序号大的：那么就可以把queue<int> q 换为 priority_queque<i…
代码随想录训练营第47天休息日|210.课程表II
代码随想录训练营第47天休息日|210.课程表II 210.课程表II思路代码 总结 210.课程表II
思路
拓扑排序 将入度为0的节点放入队列，将队列中点的入度置为-1，当前访问点的后继入度减1， 迭代直至没有入度为0的节点 仍存在入度大于0的节点&#x…
PAT备考之 关键路径 专题
虽然到目前为止，关键路径没有考过，但是近年之前没考过的拓扑排序和Floyd算法都有考，故稍微了解准备一下关键路径。
在关键路径之前，有个最长路径的求法，在没有正环的图中，边权全部取相反数，使用…
23.8.18 牛客暑期多校10部分题解
L - Grayscale Confusion
题目大意
有 n n n 个三元组 { r i , g i , b i } \{r_i,\space g_i,\space b_i\} {ri, gi, bi}，需要构造一个数组 w i w_i wi 使得 w 1 w 2 w_1w_2 w1w2 并且对于 ∀ i , j \forall i,\space j ∀i, j 满足如果 r i &…
数据结构--关键路径
数据结构–关键路径
AOE⽹
在 带权有向图 \color{red}带权有向图 带权有向图中，以 顶点表示事件 \color{red}顶点表示事件 顶点表示事件，以 有向边表示活动 \color{red}有向边表示活动 有向边表示活动，以 边上的权值表示完成该活动的开销 \…
有向图的拓扑排序 C语言
这里使用我随便画的例子： 这种用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网（Activity On Vertex Network），简称AOV-网。 按照我的理解是：AOV-网是不带权值且没有回路的有向图。 …
有向图访问计数的原理及C++实现
题目
现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。 给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。 想象在图上发生以下过程&am…
210. 课程表 II
文章目录 Tag题目来源题目解读解题思路方法一：拓扑排序 写在最后 Tag
【拓扑排序】 题目来源
210. 课程表 II 题目解读
在选修某些课程之前需要先学习某些课程，先学习的课程有数组 prerequisites 给出，其中 prerequisites[i] [ai, bi] 表…
算法－图的存储，图的转置，拓扑排序
1.图的存储 图用来对关系建模．图是节点和边构成的集合．节点反映图的元素集合，边反映图的元素集合中元素间的关系． 上述是由五个节点，三条边构成的结构．我们可以用图对其建模．
对由节点&#x…
![2017年蓝桥杯决赛（第八届）[c/c++B组]](https://img-blog.csdnimg.cn/20190521113727342.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpb25nX21pbg==,size_16,color_FFFFFF,t_70)
2017年蓝桥杯决赛（第八届）[c/c++B组]
文章目录1. 36进制2. 磁砖样式3. 希尔伯特曲线4. 发现环输入输出1. 36进制
对于16进制，我们使用字母A-F来表示10及以上的数字。 如法炮制，一直用到字母Z，就可以表示36进制。
36进制中，A表示10，Z表示35，AA…
图的应用——拓扑排序（判断有向图有无回路）
目录1. 拓扑排序的用处2. 拓扑排序的思想3. 代码实现1. 拓扑排序的用处
对于有向图，我们有时候需要确保没有回路出现，如下面的例子： 学生学习的课程之间的优先关系构成了一个有向图，显然，该有向图不能出现回路&#x…
图的应用——关键路径
目录1. 基本概念2. 求AOE网中关键路径的思路3. 代码1. 基本概念 1.AOV网和AOE网
（1）AOV网：一种有向图，图中的顶点表示活动，边表示活动之间的关系。
如 上图中，顶点为课程（活动）&a…
acwing 1192 奖金(拓扑排序)
题面 题解 跑一遍拓扑排序求出所有编号在图中的前后关系dist[i]：表示i点在拓扑图中离起点的最远距离(可能存在多起点)，dist[起点] 100,边的权值为1 代码
#include<bits/stdc.h>using namespace std;
typedef long long ll;
const int N 1e4 10…
acwing 1191 家谱树
题面 题解(拓扑排序) 拓扑图：在有向图中不存在环，并且边的指向都是从前指向后的(u->v,那么对于拓扑序u一定出现在v之前)，本题直接拓扑排序即可 对于输出字典序最小的方案，我们可以使用优先队列，每次先遍历字典序小的…
贪心算法——拓扑排序
关于贪心算法介绍： http://blog.csdn.net/mind_v/article/details/72956707
拓扑排序 问题描述
一个复杂的工程，经常可以分解成一组简单一些的任务，这些任务完成了，整个工程就完成了。例如汽车组装问题可以分解成：底…
![P3074 [USACO13FEB] Milk Scheduling S(拓扑排序)](https://img-blog.csdnimg.cn/99a15dd15d8049e5920a2f5c35ae9814.png)
P3074 [USACO13FEB] Milk Scheduling S(拓扑排序)
思路：
核心：拓扑排序
ans[x]max(ans[x],ans[t]f[x]);
注意比当前大才更新！！！
接下来几乎就是拓扑排序模板啦~
ACcode: #include<bits/stdc.h>
using namespace std;
#define int long long
const int N5e41…
【Leetcode】210.课程表II
一、题目
1、题目描述
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 p r e r e q u i s i t e s [ i ] = [ a i , b i
牛客上海高校程序设计竞赛 G CSL 的训练计划（拓扑排序）
链接：https://ac.nowcoder.com/acm/contest/551/G 来源：牛客网
时间限制：C/C 2秒，其他语言4秒 空间限制：C/C 524288K，其他语言1048576K 64bit IO Format: %lld 题目描述 众所周知，CSL 是一个负…
排序算法1 -- 拓扑排序
拓扑排序一个核心的思想是，如果一个节点的入度为0，说明该节点没有依赖任何节点或者依赖的节点都是完成了，那么就可以安排这个节点了。
void topSort() {for (图中的每个顶点v) {if (indegree[v] 0) {// 入度为0Enqueue(v, Q);}}while (!IsE…
拓扑排序的应用之杂务
P1113 杂务 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
本题使用拓扑排序，在这里简单说一下思路。
拓扑排序简单应用就是找到到达一个点有几条路径。
这个题我们要完成一个任务前要完成前置任务，我们把路径条数换成完成这个任务的时间就是答案 im…