LeetCode-210. Course Schedule II

LeetCode-210. 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] .​​

题解：

类似207题，把每次bfs的数存起来即可，最后判断下是否包含所有课程。

class Solution {public: vector findOrder(int numCourses, vector>& prerequisites) { vector> M(numCourses); vector inDegree(numCourses, 0); vector res; queue q; for (int i = 0; i < prerequisites.size(); i++) { M[prerequisites[i][1]].push_back(prerequisites[i][0]); inDegree[prerequisites[i][0]]++; } for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) { q.push(i); } } while (q.empty() == false) { int tmp = q.front(); res.push_back(tmp); q.pop(); for (int i = 0; i < M[tmp].size(); i++) { inDegree[M[tmp][i]]--; if (inDegree[M[tmp][i]] == 0) { q.push(M[tmp][i]); } } } if (res.size() == numCourses) { return res; } return {}; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。