楼主:
Rushia (みけねこ的鼻屎)
2023-07-13 22:51:55https://leetcode.com/problems/course-schedule/description/
207. Course Schedule
你要修 n 堂课,prerequisites 是一个阵列,prerequisites[i] = [ai, bi]
表示你要修 ai 之前你必须要修 bi,返回 true 或 false 表示是否可以修完所有课。
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you
should also have finished course 1. So it is impossible.
思路:
1.拓朴排序的典型题目,课程的依赖关系可以被表示为一个图,可以用DFS或BFS来解。
2.用BFS来解就是先从入度为0的点开始拓宽,只有下一个点入度也为0的时候才加入队列
(入度为 0 表示前面的课已经修完),然后为了避免循环再加入一个Set纪录已经走
过的点,每次循环时当修完 a 课程就把 a 可以到达的点入度 -1,每个节点的入度
就会不断减少。
3.最后只要检查所有点的入度都为0就表示所有课都修完了。
Java Code: