LC207 Course Schedule

2018/04/27 Leetcode

[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/)

Search

    Table of Contents