【LeetCode热题100】【图论】课程表

devtools/2024/9/25 10:29:22/

题目链接:207. 课程表 - 力扣(LeetCode)

先修课程,判断课程能不能修完,这是一个判断拓扑有序的问题,看看会不会成环

先建立有向图,记录每个顶点的入度,把入度为0的入队列

入度为0的说明没有先修课程,取出来修,并将相连的节点的入度减一,说明先修课程已经修了一个了,再判断有没有新的课程可以修的入队

最后判断修了的课程和要修的课程数目是否相等

class Solution {
public:bool canFinish(int numCourses, vector<vector<int> > &prerequisites) {vector<vector<int> > map(numCourses, vector<int>(numCourses));vector<int> inDegree(numCourses);for (auto must: prerequisites) {int from = must[1], to = must[0];++inDegree[to];map[from][to] = 1;}queue<int> learned;for (int i = 0; i < numCourses; ++i)if (inDegree[i] == 0)learned.emplace(i);int pass = 0;while (!learned.empty()) {int passed = learned.front();learned.pop();pass++;for (int i = 0; i < numCourses; ++i) {if (map[passed][i]) {--inDegree[i];if (inDegree[i] == 0)learned.emplace(i);}}}if (pass == numCourses)return true;return false;}
};


http://www.ppmy.cn/devtools/10361.html

相关文章

acwing算法提高之数据结构--并查集

目录 1 介绍2 训练3 参考 1 介绍 本专题用来记录并查集相关的题目。 并查集模板&#xff1a; //初始化 for (int i 1; i < n; i) { //n为结点数目p[i] i; }//查找 find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x]; }//合并 int pa find(a); int pb find(b)…

资金流量表的分析要点有哪些

资金流量表是国民经济核算体系的重要组成部分&#xff0c;内容涵盖了整个国民经济运行过程以及相伴随的资金运动&#xff0c;是宏观经济分析的重要工具。 一、什么是资金流量表 资金流量表是以收入分配和资金流动为核算对象&#xff0c;描述一定时期各机构部门收入的分配和使…

渐进式交付实践:通过 Argo Rollouts 和 FSM Gateway 实现金丝雀发布

渐进式交付&#xff08;Progressive delivery&#xff09;是一种软件发布策略&#xff0c;旨在更安全、更可控地将新版本软件逐步推出给用户。它是持续交付的进一步提升&#xff0c;允许开发团队在发布新版本时拥有更细粒度的控制&#xff0c;例如可以根据用户反馈、性能指标和…

Linux:服务器硬件及RAID配置

Linux&#xff1a;服务器硬件及RAID配置 服务器 服务器是什么 服务器的英文名称为“ Server”&#xff0c;是指在网络上提供各种服务的高性能计算机。作为网络的节点&#xff0c;存储、处理网络上80&#xff05;的数据、信息&#xff0c;因此也被称为网络的灵魂。 服务器和…

Hadoop3:大数据生态体系

一、技术层面 通过下面这张图&#xff0c;我们可以大概确定&#xff0c;在大数据行业里&#xff0c;自己的学习路线。 个人认为&#xff0c;Hadoop集群一旦搭建完工&#xff0c;基本就是个把人运维的事情 主要岗位应该是集中在数据计算层&#xff0c;尤其是实时计算&#xff…

LabVIEW连接PostgreSql

一、安装ODBC 下载对应postgreSQL版本的ODBC 下载网址&#xff1a;http://ftp.postgresql.org/pub/odbc/versions/msi/ 下载好后默认安装就行&#xff0c;这样在ODBC数据源中才能找到。 二、配置系统DSN 实现要新建好要用的数据库&#xff0c;这里的用户名&#xff1a;postg…

.net6项目模板搭建教程

1.集成log4net 安装如下扩展依赖即可&#xff0c;已经包含了log4net依赖&#xff1a; Microsoft.Extensions.Logging.Log4Net.AspNetCore 添加日志配置文件&#xff1a; 日志配置文件属性设置为始终复制&#xff1a; 注入服务&#xff1a; #region 注入log4net日志服务build…

设计模式|代理模式(Proxy Pattern)

文章目录 什么是代理模式举例结构优缺点优点缺点代码示例与代理模式相近的设计模式什么是代理模式 代理模式(Proxy Pattern)是一种结构型设计模式,它允许你提供一个间接访问对象的方式,以控制对对象的访问。这种模式通常在不改变原始类代码的情况下,添加一些额外的逻辑或…