Graphs Topological sort

455. Course Schedule

There are numCourses courses, numbered from 0 to numCourses - 1. Some courses must be taken before others. Each pair [a, b] in prerequisites means you must finish course b before you start course a.

Return true if you can finish every course in some order, and false if you cannot.

Example 1

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

Output: true

Explanation: Course 0 needs nothing, so we take it first. Then course 1, which needs 0, then course 2, which needs 1, and last course 3, which needs 1 and 2.

Example 2

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

Output: false

Explanation: Course 1 needs 3, course 3 needs 2, and course 2 needs 1. Each of the three waits for another, so none of them can ever start. Courses 0 and 4 are fine, but every course has to be finished.

Example 3

Input: numCourses = 2, prerequisites = []

Output: true

Explanation: Nothing has to come first, so both courses can be taken in any order.

Check your understanding

Work out the answer for this input before you write any code.

numCourses = 3 prerequisites = [[1, 0], [2, 0], [2, 1]]

Constraints

1 ≤ numCourses ≤ 10⁵
0 ≤ prerequisites.length ≤ 10⁵
prerequisites[i].length == 2
0 ≤ a_i, b_i < numCourses

Clarifying questions

What you would ask an interviewer before writing any code.