A school has n courses labelled 0 .. n - 1. Each pair [a, b] in prerequisites means course a must be completed before course b. Requirements chain: if a comes before b and b comes before c, then a is also required before c. The requirements never form a cycle.
Write is_required_before(n: int, prerequisites: list[list[int]], queries: list[list[int]]) -> list[bool]. For each query [u, v], answer True if course u must be completed before course v (directly or through a chain), and False otherwise.
prereqs = [[0, 1], [1, 2], [3, 2]]
is_required_before(4, prereqs, [[0, 2], [2, 0], [0, 3], [3, 2]]) # [True, False, False, True]
is_required_before(3, [], [[0, 1], [1, 0]]) # [False, False]
is_required_before(5, [[4, 3], [3, 0], [0, 1], [4, 2]], [[4, 1], [2, 1]]) # [True, False]
Constraints: 1 <= n <= 300, 0 <= len(prerequisites) <= 5000 (pairs may repeat), 1 <= len(queries) <= 10^5, and u != v in every query.
Searching the graph afresh for every query is far too slow with 100,000 queries. Aim for about O(n·(n + m) + q), where m is the number of pairs, or better.
Show hint
Work out, once per course, the full set of courses it's required before. If you handle the courses in the right order, each course's set is just its direct followers plus their sets.