LeetCode HOT100系列题解之课程表(9/100)

ops/2024/10/30 14:32:52/

 一、题目 

         课程表. - 力扣(LeetCode)

 二、题目解析        

          想要学习课程Bi,那么就要学习课程Ai,一个前后关系,比较好表示前后关系的就是建图。如果在学A课之前要学B课,学B课之前又要学A课,那么实际上构成了环,因此比较好想到的就是建图后DFS找环

三、题目代码

class Solution {
public:static const int N = 5010;vector<int> vec[N];int color[N];bool dfs(int u){color[u] = 0;for(int v : vec[u]){if(color[v] == 0) {return false;}else if(color[v] == -1){if(!dfs(v))return false;}}color[u] = 1;return true;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int n = prerequisites.size();for(int i = 0; i < n; i ++)vec[prerequisites[i][1]].push_back(prerequisites[i][0]);memset(color, -1, sizeof color);for(int i = 0; i < numCourses; i ++){if(color[i] == -1){if(!dfs(i))return false;}}return true;}
};


http://www.ppmy.cn/ops/129603.html

相关文章

python--pyQt 单选按钮控件 -QRadioButton

控件用来创建单选按钮&#xff0c;允许在一组选项中选择其中一个选项。 用法 text() 获取按钮文本 setText() 设置按钮文本 setCheckable() 设置按钮被选中&#xff0c;设置为True则选中&#xff0c;设置为False则取消选中 isChecked() 获取按钮是否被选中&#xff0c;选中返回…

51单片机快速入门之 串行通信 2024/10/21

51单片机快速入门之 串行通信 并行通信: 好处:传输快 适合短距离通信弊端:占用大量io 接线形式为8对8 串行通信 异步通信: 数据一帧一帧传送,传输完一帧之后,可继续或者等待(等待时为高电平) 其帧细分为(图片来源) 起始位:数据帧开始,一定为 0 外部设备只有接受到 0 之后…

力扣-最小覆盖子串

76. 最小覆盖子串 - 力扣&#xff08;LeetCode&#xff09; 给定一个字符串s,和目标字符串t&#xff0c;需要找出s中包含t中所有字符且长度最小子串&#xff0c;输出这个子串 滑动窗口&#xff0c;初始时左右指针都指向s的第一个字符,对于每个遍历到的窗口&#xff0c;判断当…

结合无监督表示学习与伪标签监督的自蒸馏方法,用于稀有疾病影像表型分类的分散感知失衡校正|文献速递-基于生成模型的数据增强与疾病监测应用

Title 题目 Hybrid unsupervised representation learning and pseudo-label supervisedself-distillation for rare disease imaging phenotype classification with dispersion-aware imbalance correction 结合无监督表示学习与伪标签监督的自蒸馏方法&#xff0c;用于稀…

UML外卖系统报告(包含具体需求分析)

1 系统背景 随着互联网技术的快速发展&#xff0c;外卖订餐服务逐渐成为人们生活中的一部分。传统的电话订餐方式面临诸多不便和限制&#xff0c;而基于互联网的外卖订餐系统则提供了更加便捷、快速和高效的订餐服务。这种系统通过将餐厅、顾客和配送人员连接起来&#xff0c;…

SpringBoot 下的Excel文件损坏与内容乱码问题

序言 随着打包部署的方式的改变&#xff0c;原本正常运行的代码可能带来一些新的问题&#xff0c;比如我们现在使用SpringBoot 的方式生成Jar包直接运行&#xff0c;就会对我们再在Resource下的Excel文件产生影响&#xff0c;导入与预期不符的情况发生cuiyaonan2000163.com 比…

Xcode 16.1 (16B40) 发布下载 - Apple 平台 IDE

Xcode 16.1 (16B40) 发布下载 - Apple 平台 IDE IDE for iOS/iPadOS/macOS/watchOS/tvOS/visonOS 发布日期&#xff1a;2024 年 10 月 28 日 Xcode 16.1 包含适用于 iOS 18.1、iPadOS 18.1、Apple tvOS 18.1、watchOS 11.1、macOS Sequoia 15.1 和 visionOS 2.1 的 SDK。Xco…

Zookeeper 理论基础

简介 ZooKeeper 由雅虎研究院开发&#xff0c;后来捐赠给了 Apache。ZooKeeper 是一个开源的分布式应用程序协调服务器&#xff0c;其为分布式系统提供一致性服务。其一致性是通过基于 Paxos 算法的ZAB 协议完成的。其主要功能包括&#xff1a;配置维护、域名服务、分布式同步、…