[Course Schedule] (https://leetcode.com/problems/course-schedule/description/)
There are a total of n courses you have to take, labeled from 0 to n - 1
e.g. 2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
我们需要维护:
map[courseID] = {those who need this course
};
degree[courseID] = how many courses it need
;
queue.in(courses needed 0 course)
while(!queue.empty()){
count++;
t := queue.top()
for(auto c : map[t]) {
degree[c]--;
if(degree[c] == 0) queue.push(c);
}
}
return count == n;
[Course Schedule II] (https://leetcode.com/problems/course-schedule-ii/description/)
题目要求输出上课顺序了
for (int i = 0; i < n; i++) {
if(degree[i] == 0) {
res.push_back(i);
q.push(i);
}
}
while(!queue.empty()){
count++;
t := queue.front(); queue.pop();
for(auto c : map[t]) {
degree[c]--;
if(degree[c] == 0) {
queue.push(c);
res.push_back(c);
};
}
}
return count == n ? res: vector<int>{};
[Course Schedule III] (https://leetcode.com/problems/course-schedule-iii/description/)