All problems

Course Schedule

Medium · topological sort

A degree has num_courses courses, numbered 0 to num_courses - 1. Some courses have requirements, given as a list prerequisites of pairs [course, pre], meaning you must finish course pre before you can take course.

You take the courses one at a time. Return True if there is some order in which you can finish all of them, and False if the requirements can never be satisfied (for example when two courses each need the other).

The same pair may appear more than once, and a pair may even name a course as its own requirement.

Examples

Example 1

Input: num_courses = 2, prerequisites = [[1, 0]]

Output: True

Take course 0, then course 1.

Example 2

Input: num_courses = 2, prerequisites = [[1, 0], [0, 1]]

Output: False

Course 1 needs course 0 and course 0 needs course 1, so neither can ever be started.

Example 3

Input: num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

Output: True

Course 0 first, then 1 and 2 in either order, and finally 3.

Constraints

• 1 <= num_courses <= 500
• 0 <= len(prerequisites) <= 2000
• Each pair holds two course numbers in the range 0 to num_courses - 1.