课程表 II
题目链接: https://leetcode.cn/problems/course-schedule-ii
解题思路:
先遍历统计每门课程依赖其他课程的数量,因为课程编号均是从0到
numCourses-1
,因此,用数组就可以进行存储同时构建每门课程被哪些课程依赖的关系拓扑
从没有依赖的课程开始处理逐个进入结果数组,并根据关系拓扑对依赖该课程的课程的依赖数量进行扣减,课程依赖数量为0的课程进入队列
重复3,直到队列为空
复杂度分析
最后更新于
题目链接: https://leetcode.cn/problems/course-schedule-ii
先遍历统计每门课程依赖其他课程的数量,因为课程编号均是从0到numCourses-1
,因此,用数组就可以进行存储
同时构建每门课程被哪些课程依赖的关系拓扑
从没有依赖的课程开始处理逐个进入结果数组,并根据关系拓扑对依赖该课程的课程的依赖数量进行扣减,课程依赖数量为0的课程进入队列
重复3,直到队列为空
最后更新于
时间复杂度: 时间复杂度为,课程数与先修课程数之和
空间复杂度: 空间复杂度为,为课程数与先修课程数之和