hardGraphsPure DSA~35 min
Minimum Semesters to Finish All Courses
Courses have prerequisite relations and unlimited parallelism per term. Find the fewest terms to complete all courses, or report it is impossible due to a cycle.
Problem
There are n courses (1..n). relations[i] = [a, b] means a must be completed before b. In each semester you may take any number of courses whose prerequisites are all done. Return the minimum number of semesters to complete all courses, or -1 if impossible.
Input
An integer n and a relations list of [a, b] prerequisite pairs.
Output
An integer: the minimum semesters, or -1.
Constraints
- 1 <= n <= 5000
- 1 <= relations.length <= 5000
- No duplicate relations.
Examples
Example 1
Input
n = 3, relations = [[1,3],[2,3]]
Output
2
Take 1 and 2 in semester 1, then 3 in semester 2.
Example 2
Input
n = 3, relations = [[1,2],[2,3],[3,1]]
Output
-1
A cycle makes completion impossible.