Fewest Terms to Finish the Program

Medium

A study program has modules modules numbered 1 to modules. Each pair [a, b] in prereqs means module a must be finished before module b can be started. In one term you can take any number of modules, as long as all of their prerequisites were completed in earlier terms. Return the smallest number of terms needed to complete the whole program. If it is impossible to complete every module, return -1.

Example 1

modules=4, prereqs=[[1, 2], [1, 3], [3, 4]] → 3

Term one: module 1; term two: modules 2 and 3; term three: module 4.

Example 2

modules=3, prereqs=[[2, 3], [3, 2]] → -1

Modules 2 and 3 require each other, so neither can ever be started.

Example 3

modules=5, prereqs=[[5, 1]] → 2

Constraints

1 ≤ modules ≤ 10⁴
1 ≤ len(prereqs) ≤ 10⁴
prereqs[i] = [a, b], 1 ≤ a, b ≤ modules, a ≠ b
All pairs in prereqs are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Topological Sort

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Best Roots for a Tree Medium Order Forced by Fragments Medium Routes That Always End Medium

Input

modules=4, prereqs=[[1, 2], [1, 3], [3, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 78 tests on the server, hidden ones included.