代码编织梦想

leetcode2115. 从给定原材料中找到所有可以做出的菜-爱代码爱编程

拓扑排序 题面 题目链接:2115. 从给定原材料中找到所有可以做出的菜 - 力扣(LeetCode) 你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ,如果你有它 所有 的原材料 ingredients[i] ,那么你可以 做出

算法基础复盘笔记day05【搜索与图论】—— dfs、bfs、树与图的深度优先遍历、树与图的广度优先遍历、拓扑排序_用bfs排序,n个节点有多少种排列数序-爱代码爱编程

❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于Java后端开发,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得关注、点赞、收藏、评论⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让

c++算法:矩阵中的最长递增路径_c++矩阵最长递增路径-爱代码爱编程

涉及知识点 拓扑排序 题目 给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不

【数据结构】图的应用:最小生成树;最短路径;有向无环图描述表达式;拓扑排序;逆拓扑排序;关键路径_最小生成树算法能判断有向图环路吗-爱代码爱编程

目录 1、最小生成树 1.1 概念  1.2 普利姆算法(Prim) 1.3 克鲁斯卡尔算法(Kruskal)  2、最短路径 2.1 迪杰斯特拉算法(Dijkstra) 2.2 弗洛伊德算法(Floyd)  2.3 BFS算法,Dijkstra算法,Floyd算法的对比 3、有向无环图描述表达式 3.1 有向无环图定义及特点 3.2

洛谷——p1347 排序(图论-爱代码爱编程

文章目录 一、题目排序题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示 二、题解

hdu 2647 reward-爱代码爱编程

拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止. 第一次做拓扑排序,有几点要说明一下: 1.vector是一个容器,可以动态分配内存,存储方式是线性的,他有几个常用的函数: s[b].p

poj 2367 genealogical tree_the system of martians' blood relations is confusi-爱代码爱编程

裸的拓扑排序。 #include <iostream> #include<stdio.h> #include<cstring> #include<vector> using namespace std; vector<int>a[105]; int from[105],to[105],fla

hdu 2094 产生冠军_hdu2094-爱代码爱编程

产生冠军的前提是有且只有一个人赢...... #include <iostream> #include<stdio.h> #include<cstring> using namespace std; char temp1[30],temp2[30]; char topo[2005][30]; int win[200

省选模拟(12.08) t2 演艺_idhash[x]=nodecnt++;-爱代码爱编程

演艺 题目背景: 12.08 省选模拟T2 分析:最短路 + 拓扑排序 + bitset + 哈希   感觉是本场最难的题······考虑如何为满足条件的A,B,就是在S à T的最短路DAG上,经过A的S à T的方案数与经过B的S à T之和是S à T的总方案数,并且A不能到B。考虑如何实现,首先我们以S为起点跑dijkst

p4017 最大食物链计数(拓扑排序)-爱代码爱编程

最大食物链计数 题目背景 你知道食物链吗?Delia 生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。 题目描述 给你一个食物

[洛谷]p4017 最大食物链计数(拓扑排序)_洛谷p4017-爱代码爱编程

#include<iostream> #include<queue> using namespace std; const int N=5e3+10; int f[N],ru[N],chu[N],mp[N][N],n,m,ans,a,b; int main() { ios::sync_with_stdio(false),cin

最大食物链计数(c++,dp,拓扑排序)-爱代码爱编程

题目背景 你知道食物链吗?Delia 生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。 题目描述 给你一个食物网,你要求出这个食

23.8.18 牛客暑期多校10部分题解-爱代码爱编程

L - Grayscale Confusion 题目大意 有 n n

【leetcode每日一题合集】2023.9.11-爱代码爱编程

文章目录 630. 课程表 III解法——反悔贪心⭐⭐⭐⭐⭐ 1462. 课程表 IV⭐解法1——拓扑排序预处理解法2——Floyd算法判断是否存在路径 2596. 检查骑士巡视方案(方向模拟)12

【leetcode每日一题合集】2023.9.4-爱代码爱编程

文章目录 449. 序列化和反序列化二叉搜索树⭐⭐⭐⭐⭐(二叉树的重建)解法相关题目——297. 二叉树的序列化与反序列化⭐⭐⭐⭐⭐解法——深度优先搜索 2605. 从两个数字数组里生成最小数字哈

7-爱代码爱编程

题目概述: 求有依赖关系的工程的最早完工时间。如果不可能,则输出impossible。 思路: 一开始想的是dijkstra求最长路,但是不对,因为dijkstra是单源点,而此题可以有多个源点和汇点。 判是否可行:若不存在源点或汇点则不可行,即至少要有一个入度为0的点和一个出度为0的点。 求最早完成时间: 拓扑排序+关键路径。 利用队列实现

编译原理复习六:依赖图、注释语法树上节点的求值讲解(附题目与答案 超详细)_语法依赖树-爱代码爱编程

需要原卷和答案请点赞关注收藏后评论区留言私信~~~ 一、依赖图 依赖图是用来描述相应语法树中属性的信息流;从一个属性的边到另一个需要通过计算第一个属性得到第二个属性。边的表达要遵循语法规则。  1.对于每一个分析树的节点而言,假设有一个节点定义为语法符号X,依赖图就存在与X相关的每一个属性的节点。 2.假设一个与产生式P相关的语义规则根据

pat备考之 关键路径 专题_pat 关键路径-爱代码爱编程

虽然到目前为止,关键路径没有考过,但是近年之前没考过的拓扑排序和Floyd算法都有考,故稍微了解准备一下关键路径。 在关键路径之前,有个最长路径的求法,在没有正环的图中,边权全部取相反数,使用Bellman-Ford算法即可。 而对于关键路径问题(有向无环图),除了动态规划的解法,比较常规的是使用拓扑排序。 具体过程:在拓扑排序的基础之上,进行一次正

poj2585 zoj2193 window pains 拓扑排序_zoj2193的约束关系图-爱代码爱编程

poj2585 拓扑排序  因为一个窗口和一个窗口有上下之分,也就是有先后之分,若显示没有问题,则存在拓扑排序,否则不存在。 最下层窗口为有向图的起点,最上层为终点。构建关系图即可。 代码: #include<iostream> #include<cstdio> #include<cstring>

7-爱代码爱编程

题目概述: 判断有没有成正环。 思路: 拓扑排序。统计从队列中取出的数的个数,如果个数等于n,则是没有成环的,可完成任务调度。 如果成环了,在环外的分支出去之后,队列就为空了(成环的节点入度始终不为0),因此入队的数小于n。 #include<iostream> #include<cstring> #include<