How many terms
A curriculum has n courses, and some have prerequisites: course a must be passed before course b. In a term you can take any number of courses, but only those whose prerequisites have all been passed in previous terms. In how many terms can the whole curriculum be completed?
A build system faces the same problem: in one tick of a parallel build, all packages whose dependencies are ready can be built. Among the tests are the 66 chapters of this site’s basic course, the Go standard library with its 2790 imports, and the Debian packages of the sandbox where your code runs.
Input
The first line holds n and m (1 ≤ n ≤ 100,000, 0 ≤ m ≤ 200,000). Then m lines a b: course a is a prerequisite of course b (1 ≤ a, b ≤ n, a ≠ b). Pairs may repeat.
Output
The smallest number of terms, or -1 if the curriculum cannot be completed: the prerequisites close into a circle.
Examples
Example 1
6 6 1 2 1 3 2 4 3 4 4 5 1 6
4
Example 2
4 4 1 2 2 3 3 1 1 4
-1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
In the first term you can take all courses without prerequisites. Which courses open up by the second?
2Hint 2
A course’s term is one more than the latest term among its prerequisites. If this is computed by recursion without memoisation, how many times will a course be computed in a test with twenty layers of fifty courses?
3The idea
This is Kahn’s algorithm run in waves. Wave 1 is the courses that wait for nothing. Once a wave is passed, decrement each course’s counter of unpassed prerequisites, and those that reach zero form the next wave. The number of waves is the answer: a course cannot be taken earlier, because a chain of prerequisites of that length leads up to it, and it need not be later, because in its wave everything it needs has been passed.
4Walkthrough
Read the pairs, count for each course how many prerequisites it has and remember which courses it opens. The first wave is the courses with counter 0. Go through the wave, decrement the counters, collect the next one. If at the end not all courses are passed, the remaining ones are waiting for each other in a circle: output −1.
The answer equals the number of courses on the longest chain of prerequisites. For the chapters of the basic course it is 18: from “What a program can do” through lists, dictionaries, objects, the stack, graphs and automata to “The salesman’s expedition”. The Go standard library builds in at least 29 ticks however many cores there are, and the Debian packages cannot be configured at all without dpkg’s rules: libc6 and libgcc-s1 depend on each other.
Repeated pairs do no harm: each one both increments a counter and decrements it.
4+Solution
5Complexity
Each course enters a wave once, each pair is examined once: O(n + m).
6Common mistakes
- Recursion without memoisation. The number of paths grows exponentially: in the test with twenty layers there are 5019 of them. Already on the Go standard library such a solution runs out of time; that is
wrong.py. With memoisation the recursion becomes the same dynamic programming in topological order, but in Python it needs a large depth allowance: one of the tests has a chain of a hundred thousand courses. - A missed cycle. If you do not check that all courses have been passed, a curriculum with a circle gives a number instead of −1.
- One queue without waves. The ordinary Kahn’s algorithm works too if you remember each course’s wave number: a course’s wave is one more than the wave of the prerequisite that freed it last.