DSA Tracker

Visualize

Course Schedule (Prerequisite Tasks)

Floyd-Warshall transitive closure: build reachability once, answer every query in O(1)

time O(V^3 + Q)space O(V^2)

Each query only asks whether a directed path exists between two tasks, which makes this a reachability problem, not a shortest-path one. Answering queries one at a time means re-searching the graph for every query; instead, build the full n x n transitive closure ONCE — reach[i][j] means i can reach j through any number of hops — and every query becomes a single lookup. Floyd-Warshall does this by trying each node k in turn as a bridge: if i reaches k and k reaches j, then i reaches j too, even with no direct arrow between them.

Details

Animated on: 6 tasks with prerequisites 0->1, 1->2, 2->3, 0->4, 4->3, 5->2 (a->b means a before b) — for queries (0,3), (3,0), (5,3), (0,5) and (1,4), must the first task come before the second?

Problem:Course Schedule (Prerequisite Tasks)Medium

Floyd-Warshall transitive closure: build reachability once, answer every query in O(1)

step 1 / 11

Direct prerequisites

6 tasks, and prerequisite [a, b] means a must be done before b. The 5 queries below don't each need their own search — building the full reachability picture ONCE answers all of them in O(1) apiece.

Pseudocode
1FUNCTION checkTasks(n, prereqs, queries):
2  FOR EACH (a, b) IN prereqs
3    reach[a][b] <- true
4  FOR k FROM 0 TO n - 1
5    FOR i FROM 0 TO n - 1
6      FOR j FROM 0 TO n - 1
7        IF reach[i][k] AND reach[k][j]
8          reach[i][j] <- true
9  FOR EACH (u, v) IN queries
10    APPEND reach[u][v] TO answers
11  RETURN answers

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 6 tasks, and prerequisite [a, b] means a must be done before b. The 5 queries below don't each need their own search — building the full reachability picture ONCE answers all of them in O(1) apiece.
  2. Mark reach[a][b] = true for every direct pair: 0->1, 1->2, 2->3, 0->4, 4->3, 5->2. Everything else starts false — a task only reaches another right now if there is a literal arrow between them.
  3. Route through node 1: task 0 reaches 1, and 1 reaches 2, so 0 now reaches 2 too even with no direct arrow between them.
  4. Route through node 2: everything that reaches 2 (0, 1, 5) now also reaches whatever 2 reaches. 3 new links appear: 0->3, 1->3, 5->3.
  5. The remaining passes add nothing further — node 0 and 5 have no arrows pointing IN, and node 3 has no arrows pointing OUT, so routing through any of them can't extend anyone's reach. Final reach counts: task 0 reaches 4, task 1 reaches 2, task 2 reaches 1, task 3 reaches 0, task 4 reaches 1, task 5 reaches 2.
  6. Query 0 -> 3: reach[0][3] is true (found via 0->4->3), so task 0 must come before task 3. Answer: true.
  7. Query 3 -> 0: reach[3][0] is false — no chain of arrows leads from 3 to 0. Answer: false.
  8. Query 5 -> 3: reach[5][3] is true (found via 5->2->3), so task 5 must come before task 3. Answer: true.
  9. Query 0 -> 5: reach[0][5] is false — no chain of arrows leads from 0 to 5. Answer: false.
  10. Query 1 -> 4: reach[1][4] is false — no chain of arrows leads from 1 to 4. Answer: false.
  11. The 5 answers come back as [true, false, true, false, false] — read straight off the matrix built once, not from 5 separate searches. RETURN answers.

Now solve it yourself

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

Solve Course Schedule (Prerequisite Tasks) in the editorAll Graph problemsBack to roadmap