DSA Tracker

Visualize

Course Schedule

Kahn's topological sort: drain the courses that have no prerequisites

time O(V + E)space O(V + E)

You never have to produce the order to answer this. Repeatedly take any course whose prerequisites are all done, and count how many you get through: anything reachable drains eventually, so the count falls short only when some courses depend on each other in a loop. One number per course is enough state — how many prerequisites are still outstanding — because finishing a course lowers exactly the counts of the courses it unlocks. The picture below draws one directed arrow per prerequisite and shows that outstanding count as a badge.

Details

Animated on: 7 courses with prerequisites 0->1, 0->2, 1->3, 2->3, 3->4, 4->5, 5->6, 6->4 (a->b means take a before b) — can every course be finished?

Problem:Course ScheduleMedium

Pattern:Topological Sort

Kahn's topological sort: drain the courses that have no prerequisites

step 1 / 12

Courses and prerequisites

7 courses, and an arrow a to b means a must be taken before b. The question is not which order to use but whether ANY order exists — and the only thing that can rule one out is a group of courses that require each other in a loop.

Pseudocode
1FUNCTION canFinish(n, prereqs):
2  FOR c FROM 0 TO n - 1
3    indeg[c] <- 0
4  FOR EACH (a, b) IN prereqs
5    APPEND b TO next[a]
6    indeg[b] <- indeg[b] + 1
7  queue <- EVERY c WHERE indeg[c] = 0
8  taken <- 0
9  WHILE queue NOT EMPTY
10    c <- REMOVE FIRST FROM queue
11    taken <- taken + 1
12    FOR EACH d IN next[c]
13      indeg[d] <- indeg[d] - 1
14      IF indeg[d] = 0
15        APPEND d TO queue
16  RETURN taken = n

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. 7 courses, and an arrow a to b means a must be taken before b. The question is not which order to use but whether ANY order exists — and the only thing that can rule one out is a group of courses that require each other in a loop.
  2. Count the arrows pointing INTO each course: 0 needs 0, 1 needs 1, 2 needs 1, 3 needs 2, 4 needs 2, 5 needs 1, 6 needs 1. That single number is all that decides whether a course is takeable right now, so it is the only state worth tracking.
  3. Only course 0 sits at 0, so it is the one thing we can start with — every other course is waiting on something. Queue it.
  4. Take course 0 — its count is 0, so nothing blocks it. That is 1 of 7 done, and the queue is now empty.
  5. Finishing 0 clears one prerequisite off 1 and 2: 1 now needs 0, 2 now needs 0. 1 and 2 reached 0, so they join the queue.
  6. Take course 1 — its count is 0, so nothing blocks it. That is 2 of 7 done, and 2 still waits in the queue.
  7. Finishing 1 clears one prerequisite off 3: 3 now needs 1. Nothing reached 0, so nothing new became takeable.
  8. Take course 2 — its count is 0, so nothing blocks it. That is 3 of 7 done, and the queue is now empty.
  9. Finishing 2 clears one prerequisite off 3: 3 now needs 0. 3 reached 0, so it joins the queue.
  10. Take course 3 — its count is 0, so nothing blocks it. That is 4 of 7 done, and the queue is now empty.
  11. Finishing 3 clears one prerequisite off 4: 4 now needs 1. Nothing reached 0, so nothing new became takeable.
  12. The queue is empty but only 4 of 7 courses came out of it. Courses 4, 5, 6 still carry a count above 0, and the highlighted arrows say why: each one waits on another course inside the same loop, so none of them can ever be the one that goes first. RETURN false.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Course Schedule in the editorAll Graph problemsBack to roadmap