> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Course Schedule IV Python Solution with Tests

> Tested Python solution for LeetCode 1462 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 1462, Medium. Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort. [View on LeetCode](https://leetcode.com/problems/course-schedule-iv/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1462   # by problem number
lcpy gen -s course_schedule_iv   # by problem name
```

## Problem

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `ai` first if you want to take course `bi`.

* For example, the pair `[0, 1]` indicates that you have to take course `0` before you can take course `1`.

Prerequisites can also be **indirect**. If course `a` is a prerequisite of course `b`, and course `b` is a prerequisite of course `c`, then course `a` is a prerequisite of course `c`.

You are also given an array `queries` where `queries[j] = [uj, vj]`. For the `jth` query, you should answer whether course `uj` is a prerequisite of course `vj` or not.

Return *a boolean array* `answer`, *where* `answer[j]` *is the answer to the* `jth` *query*.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/05/01/courses4-1-graph.jpg)

```
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.
```

```
Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.
```

![Example 3](https://assets.leetcode.com/uploads/2021/05/01/courses4-3-graph.jpg)

```
Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]
```

### Constraints

* `2 <= numCourses <= 100`
* `0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)`
* `prerequisites[i].length == 2`
* `0 <= ai, bi <= numCourses - 1`
* `ai != bi`
* All the pairs `[ai, bi]` are **unique**.
* The prerequisites graph has no cycles.
* `1 <= queries.length <= 10^4`
* `0 <= ui, vi <= numCourses - 1`
* `ui != vi`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/course_schedule_iv/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/course_schedule_iv/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^3) Floyd-Warshall transitive closure (n <= 100)
    # Space: O(n^2)
    def check_if_prerequisite(
        self, num_courses: int, prerequisites: list[list[int]], queries: list[list[int]]
    ) -> list[bool]:
        # reach[a][b] = True if a is a (direct or indirect) prerequisite of b.
        reach = [[False] * num_courses for _ in range(num_courses)]
        for a, b in prerequisites:
            reach[a][b] = True

        for k in range(num_courses):
            for i in range(num_courses):
                if reach[i][k]:
                    for j in range(num_courses):
                        if reach[k][j]:
                            reach[i][j] = True

        return [reach[u][v] for u, v in queries]
```

## Complexity

| Time                                                 | Space  |
| ---------------------------------------------------- | ------ |
| O(n^3) Floyd-Warshall transitive closure (n \<= 100) | O(n^2) |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).