mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
43 lines
2.5 KiB
Markdown
Executable File
43 lines
2.5 KiB
Markdown
Executable File
# [210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)
|
||
|
||
|
||
## 题目
|
||
|
||
There are a total of *n* courses you have to take, labeled from `0` to `n-1`.
|
||
|
||
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: `[0,1]`
|
||
|
||
Given the total number of courses and a list of prerequisite **pairs**, return the ordering of courses you should take to finish all courses.
|
||
|
||
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
|
||
|
||
**Example 1:**
|
||
|
||
Input: 2, [[1,0]]
|
||
Output: [0,1]
|
||
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
|
||
course 0. So the correct course order is [0,1] .
|
||
|
||
**Example 2:**
|
||
|
||
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
|
||
Output: [0,1,2,3] or [0,2,1,3]
|
||
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
|
||
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
|
||
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
|
||
|
||
**Note:**
|
||
|
||
1. The input prerequisites is a graph represented by **a list of edges**, not adjacency matrices. Read more about [how a graph is represented](https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs).
|
||
2. You may assume that there are no duplicate edges in the input prerequisites.
|
||
|
||
## 题目大意
|
||
|
||
现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]。给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
|
||
|
||
|
||
## 解题思路
|
||
|
||
- 给出 n 个任务，每两个任务之间有相互依赖关系，比如 A 任务一定要在 B 任务之前完成才行。问是否可以完成所有任务，如果可以完成任务，就输出完成任务的顺序，如果不能完成，输出空数组。
|
||
- 这一题是第 207 题的加强版。解题思路是 AOV 网的拓扑排序。最后输出数组即可。代码和第 207 题基本不变。具体解题思路见第 207 题。
|