Pattern visualizer

Requirements Met (Prerequisite Tasks)

A query [u, v] is just asking whether v is reachable from u along the prerequisite arrows. With only 100 tasks, the cheapest correct approach is to search from u for each query directly — a plain BFS that stops the moment it dequeues v, or empties the queue without ever seeing it. The picture below runs exactly that search: the queue panel is what a BFS is at any instant, and the path highlighted at the end is the proof for a true answer. Animated on: 3 tasks with prerequisites 0->1, 1->2 (a->b means a before b) — for each query [u, v], is u required before v? Queries: [0,2], [2,0], [1,2]..

One BFS reachability search per query

time O(Q * (V + E))space O(V + E)step 1 / 13

Prerequisite graph

line 1

3 tasks, and an arrow a -> b means a must happen before b. Each query [u, v] just asks: is there a directed path from u to v? Answering that is a plain reachability search, one BFS per query.

Pseudocode

1FUNCTION isReachable(next, u, v):
2  IF u = v
3    RETURN true
4  visited <- {u}
5  queue <- [u]
6  WHILE queue NOT EMPTY
7    c <- REMOVE FIRST FROM queue
8    IF c = v
9      RETURN true
10    FOR EACH d IN next[c]
11      IF d NOT IN visited
12        ADD d TO visited
13        APPEND d TO queue
14  RETURN false

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap