Minimum Semesters to Graduate
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A department offers courses numbered 1 to n, and you must take all of them to graduate.
prereq[i] = [a, b] means course b can be taken only in a semester after course a was completed.
There is no limit on how many courses you take per semester. Return the minimum number of semesters needed to complete every
course, or -1 if the prerequisites make some course impossible to take.
Examples
| n | prereq | result |
|---|---|---|
3 | [[1, 3], [2, 3]] | 2 |
5 | [[1, 2], [2, 3], [1, 4], [4, 5], [3, 5]] | 4 |
3 | [[1, 2], [2, 3], [3, 1]] | -1 |
Example 1 — Take 1 and 2 in the first semester, then 3.
Example 2 — The chain 1 → 2 → 3 → 5 has four courses, so four semesters are needed.
Example 3 — Courses 1, 2 and 3 require each other, so none of them can ever be started.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(n: int, prereq: int[][]) → int
Constraints
-
n -
prereq.length prereq[i] = [a, b], ,- No pair
[a, b]appears more than once.
Expected complexity
- Time
- O(N + M)
- Space
- O(N + M)
Examples
| n | prereq | Expected |
|---|---|---|
3 | [[1,3],[2,3]] | 2 |
5 | [[1,2],[2,3],[1,4],[4,5],[3,5]] | 4 |
3 | [[1,2],[2,3],[3,1]] | -1 |
Hint
Hint
The answer is the number of vertices on the longest path of the prerequisite graph, or -1 if it has a cycle.
Run Kahn's topological sort: when removing edge a → b, set term[b] = max(term[b], term[a] + 1). If fewer than n
courses are ever dequeued, there is a cycle. Repeatedly sweeping all edges until nothing changes is on long chains.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1466 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |