codejump
HardPro challengePythonJavaScriptTypeScript

Graph — Parallel Courses (Topological Sort)

Data StructuresGraphTopological SortBFS

There are n courses labelled 1..n. relations is a list of [prev, next]
pairs meaning **course prev must be finished before course next can
start**.

In one semester you can take any number of courses, as long as every
prerequisite was finished in an earlier semester.

Return the minimum number of semesters needed to take all the courses, or
-1 if it is impossible because the prerequisites contain a cycle.

This is a topological sort in layers (Kahn's algorithm): each semester is one
BFS level of the courses whose prerequisites are all done.

Examples

solve(3, [[1, 3], [2, 3]])            → 2    // 1 and 2 together, then 3
solve(3, [[1, 2], [2, 3], [3, 1]])    → -1   // a cycle: nothing can start
solve(4, [])                          → 1    // no prerequisites, all at once

Constraints

  • 1 <= n <= 5000
  • Relations may repeat; an unreachable cycle among a *subset* of courses still

makes the whole answer -1.

Sample tests

Test #1Two prerequisites feeding one course
Input: [3,[[1,3],[2,3]]]
Output: 2
Test #2A three-course cycle
Input: [3,[[1,2],[2,3],[3,1]]]
Output: -1
Test #3No prerequisites — everything in one semester
Input: [4,[]]
Output: 1