Funcia
Lv.2daggraphtopological-sort

Minimum Semesters to Graduate

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A department offers nn 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

nprereqresult
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

  • 1≤1 \le n ≤100,000\le 100{,}000
  • 0≤0 \le prereq.length ≤200,000\le 200{,}000
  • prereq[i] = [a, b], 1≤a,b≤n1 \le a, b \le n, a≠ba \ne b
  • No pair [a, b] appears more than once.

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

nprereqExpected
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 O(N⋅M)O(N \cdot M) on long chains.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251466 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.