- 2024-10-15代码随想录训练营第63天|拓扑排序
117.软件构建#include<iostream>#include<vector>#include<queue>#include<unordered_map>usingnamespacestd;intmain(){intm,n,s,t;cin>>n>>m;vector<int>inDegree(n,0);//记录每个文件的入度
- 2024-09-15图:207课程表 题解:入度数组,邻接表,队列,拓扑排序
207.课程表-力扣(LeetCode)没做出来,参考题解,这篇题解写的非常好。把一个有向无环图转成线性的排序就叫 拓扑排序。(没太懂这句话的意思)classSolution{public:boolcanFinish(intnumCourses,vector<vector<int>>&prerequisites){vector<int>inDegre
- 2024-08-30day58-graph theory-part08-8.29
tasksfortoday:1.拓扑排序117.软件构建2.dijkstra算法47.参加科学大会---------------------------------------------------------------------------------1.拓扑排序117.软件构建Inthispractice,itinvolvesmainlytheBFSmethod,whichiterativelysearc
- 2024-05-25AOV网与拓扑排序
AOV网的定义以顶点表示活动,以有向边表示活动之间的优先关系的有向图称为顶点表示活动的网(ActivityOnVertexNetwork),简称AOV网。例如:计算机专业课学习流程为保证流程可执行,AOV网中不应该出现回路。拓扑排序拓扑序列:设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1,v2
- 2024-05-17数据结构学习笔记-有向图的度
求有向图的度问题描述:已知有向图G用邻接矩阵存储,设计算法以分别求解顶点vi的入度、出度和度。【算法设计思想】出度的计算(getOutDegree)遍历法:通过遍历邻接矩阵中顶点vi所在行的所有元素来计算vi的出度。对于每个元素matrix[vi][j],如果其值不为0(表示存在从顶点vi到顶点
- 2024-05-06207. 课程表-python
你这个学期必须选修numCourses门课程,记为0到numCourses-1。在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出,其中prerequisites[i]=[ai,bi],表示如果要学习课程ai则必须先学习课程bi。例如,先修课程对[0,1]表示:想要学习课程0,你
- 2023-07-0139. 拓扑排序
一、什么是拓扑排序 拓扑排序是对有向无圈图的顶点的一种排序,它使得如果存在一条从\(v_{i}\)到\(v_{j}\)的路径,那么排序中\(v_{j}\)出现在\(v_{j}\)的后面。有向边(v,w)表明任务v必须在任务w前完成。显然,如果图含有圈,那么拓扑排序是不可能的,因为对于圈上的两个
- 2023-06-20数据结构代码整理_基于邻接表的拓扑排序(C++_DFS_BFS_递归)
目录Chat图解基于栈实现(dfs)基于队列实现(bfs)基于递归实现(dfs)Chat1.代码所属的类在数据结构代码整理_基于邻接表存储结构的有向图的实现(C++)2.拓扑排序的思想就是不断找入度为0的节点并将其输出并标记,标记后与他相连的节点的入度都会减一,不断进行标记直至所有的节点都被输出为止
- 2023-05-29poj 1691
题目大意:墙上有一块区域被分成了n个矩形,每个矩形要涂上各自的颜色。为了保证完美要求这一块区域可以进行涂色的条件是它上方的所有区域都已经涂好颜色,这样就不会有后续的操作影响这块区域的颜色。但是如果两块区域颜色不同就要换涂颜色用的刷子。问最少需要换几次。解题思路:由于这
- 2023-04-09Leetcode(剑指offer专项训练)——DFS/BFS专项(2)
课程顺序题目现在总共有numCourses 门课需要选,记为 0 到 numCourses-1。给定一个数组 prerequisites,它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i]=[ai,bi] 表示想要学习课程ai ,需要先完成课程bi 。请根据给出的
- 2023-02-20LeetCode 2050 并行课程3
1题目原题链接。2想法题目本质上是一条拓扑排序的题,只不过,在拓扑排序的基础上,加上了一个时间的限制。每门课程规定了需要一定的时间完成,也就是说,完成一门课程的时间,
- 2023-01-27拓扑排序
拓扑排序是一种图论算法,它用于对有向无环图(DAG)进行排序。该算法的目的是找到图中所有顶点的线性排列,使得对于图中的任意两个顶点u和v,如果存在一条从u到v的边,那么在
- 2023-01-20D - Change Usernames -- ATCODER
D-ChangeUsernameshttps://atcoder.jp/contests/abc285/tasks/abc285_d 思路DFS深度遍历图。需要注意的是,整个大图中可能有很多小的连通子图,每个子图需要确定起
- 2023-01-17【拓扑排序】LeetCode 210. 课程表 II
题目链接210.课程表II思路在BFS过程中将所有入度为0的点放入结果集中,如果最终结果集中点的数目和课程数一样,则说明这个结果集可行。代码classSolution{pub
- 2022-12-21拓扑排序
拓扑排序TODO待补全Codeimportjava.io.*;importjava.util.LinkedList;importjava.util.List;importjava.util.Stack;publicclassMain{staticStreamT
- 2022-10-02Leetcode 207. 课程表
https://leetcode.cn/problems/course-schedule/你这个学期必须选修numCourses门课程,记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。先修课程