Why it works
- A course enters the queue only when every course before it is taken, so the courses come out of the queue in an order that keeps every pair.
- On a loop each course waits for the one before it on the loop. None of them ever reaches in-degree 0, so none is taken, and neither is any course after the loop.
- So all n courses are taken exactly when there is no loop: counting the taken courses answers the question.
Complexity
Time O(n + p) for n courses and p pairs: each course enters the queue at most once and each arrow is followed at most once. Memory O(n + p) for the arrows, the in-degrees and the queue.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗