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

210. 课程表 II

现在你总共有  门课需要选,记为  到 。给你一个数组  ,其中  ,表示在选修课程  前 必须 先选修  。

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

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。

示例 1:

[0,1] 。

示例 2:

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

示例 3:

输入:numCourses = 1, prerequisites = []
输出:[0]
  • 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 = []
输出:[0]
  • 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 };