# 210. 课程表 II(拓扑排序)(210. Schedule II (topological sorting))-其他

## 210. 课程表 II(拓扑排序)(210. Schedule II (topological sorting))

### 210. 课程表 II

``numCourses``
``0``
``numCourses - 1``
``prerequisites``
``prerequisites[i] = [ai, bi]``
``ai``
``bi``
• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

``[0,1] 。``

``[0,1,2,3]``
``[0,2,1,3]``

``````输入：numCourses = 1, prerequisites = []

``````
• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• 所有[ai, bi] 互不相同
`````` 1 class Solution {
2 public:
3     vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
4         vector<int> ans; // 学习课程列表
5         if (prerequisites.empty() || numCourses == 0) {
6             for (int i = 0; i < numCourses; i++) {
7                 ans.push_back(i);
8             }
9             return ans;
10         }
11         vector<int> indegree(numCourses, 0); // 记录每个课程的入度
12         for (auto &prerequisite : prerequisites) {
13             indegree[prerequisite[0]]++;
14         }
15         queue<int> q; // 存储入度为0的课程
16         // 入度为0的课程入队
17         for (int i = 0; i < numCourses; i++) {
18             if (indegree[i] == 0) {
19                 q.push(i);
20             }
21         }
22         int cnt = 0; // 学习课程数
23         while (!q.empty()) {
24             int temp = q.front();
25             q.pop();
26             ans.push_back(temp);
27             cnt++;
28             for (auto &course : prerequisites) {
29                 // course[1] -> course[0],剪枝去除边,找到依赖course[1]的课程入度都要--
30                 if (course[1] != temp) {
31                     continue;
32                 }
33                 indegree[course[0]]--;
34                 if (indegree[course[0]] == 0) {
35                     q.push(course[0]);
36                 }
37             }
38         }
39         if (cnt < numCourses) {
40             ans.clear();
41         }
42         return ans;
43     }
44 };``````
————————

### 210. Curriculum II

Now you have a total of ， courses to choose. Remember ， to. I’ll give you an array, in which, means that you must # take an elective course before # taking an elective course.

``numCourses``
``0``
``numCourses - 1``
``prerequisites``
``prerequisites[i] = [ai, bi]``
``ai``
``bi``
• For example, if you want to learn course 0, you need to complete course 1 first. We use a match to represent: [0,1].

Return to the learning sequence you arranged to complete all courses. There may be multiple correct sequences. You just need to return any one of them. If it is impossible to complete all courses, an empty array is returned.

Example 1:

``[0,1] 。``

Example 2:

``[0,1,2,3]``
``[0,2,1,3]``

Example 3:

``````输入：numCourses = 1, prerequisites = []

``````
• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All [AI, Bi] are different from each other
`````` 1 class Solution {
2 public:
3     vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
4         vector<int> ans; // 学习课程列表
5         if (prerequisites.empty() || numCourses == 0) {
6             for (int i = 0; i < numCourses; i++) {
7                 ans.push_back(i);
8             }
9             return ans;
10         }
11         vector<int> indegree(numCourses, 0); // 记录每个课程的入度
12         for (auto &prerequisite : prerequisites) {
13             indegree[prerequisite[0]]++;
14         }
15         queue<int> q; // 存储入度为0的课程
16         // 入度为0的课程入队
17         for (int i = 0; i < numCourses; i++) {
18             if (indegree[i] == 0) {
19                 q.push(i);
20             }
21         }
22         int cnt = 0; // 学习课程数
23         while (!q.empty()) {
24             int temp = q.front();
25             q.pop();
26             ans.push_back(temp);
27             cnt++;
28             for (auto &course : prerequisites) {
29                 // course[1] -> course[0],剪枝去除边,找到依赖course[1]的课程入度都要--
30                 if (course[1] != temp) {
31                     continue;
32                 }
33                 indegree[course[0]]--;
34                 if (indegree[course[0]] == 0) {
35                     q.push(course[0]);
36                 }
37             }
38         }
39         if (cnt < numCourses) {
40             ans.clear();
41         }
42         return ans;
43     }
44 };``````