Course schedule
MediumStuck?
Show a hintHide the hint
Count how many prerequisites each course has. Repeatedly take one with none left, and reduce the counts of whatever depended on it.
The ideas behind this problem
Next in this lesson
How many separate groups of friendsYou are given a number of courses and a list of prerequisite pairs. Each pair a b means course a requires course b first.
Decide whether it is possible to finish every course.
Constraints#
1 <= n <= 1000000 <= m <= 200000
Input
numCourses is one integer. prerequisites is a row count, then 2, then that many pairs.
Output
`true` if every course can be finished, otherwise `false`.
Examples
Input
2 1 2 1 0
Output
true
Take course 0, then course 1.
Input
2 2 2 1 0 0 1
Output
false
Each course requires the other, so neither can be taken first.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.