1462. Course Schedule IV - Detailed Explanation

Problem Statement

Description:
You are given an integer n representing the total number of courses labeled from 0 to n - 1. You are also given a list of prerequisites where each element is a pair [u, v] indicating that course u is a prerequisite of course v. Additionally, you are provided with a list of queries where each query is a pair [u, v]. For each query, you need to determine whether course u is a prerequisite of course v (i.e. whether there exists a direct or indirect path from u to v in the directed graph).

Examples:

Example 1:

• Input:
  n = 2
prerequisites = [[1, 0]]
queries = [[0, 1], [1, 0]]
• Output: [false, true]
• Explanation:
  Course 1 is a prerequisite for course 0. Hence, in the query [1, 0] the answer is true, while in the query [0, 1] the answer is false.

Example 2:

• Input:
  n = 2
prerequisites = []
queries = [[1, 0], [0, 1]]
• Output: [false, false]
• Explanation:
  There are no prerequisites. Every query returns false.

Example 3:

• Input:
  n = 3
prerequisites = [[1, 2], [1, 0], [2, 0]]
queries = [[1, 0], [1, 2], [2, 1]]
• Output: [true, true, false]
• Explanation:
  • From course 1, you can directly go to 0 and 2 (and even indirectly from 1 to 0 via 2 is possible, though here a direct edge exists).
  • There is no path from course 2 to course 1.

Constraints:

• 2 ≤ n ≤ 100
• The number of prerequisites can be up to several thousand.
• prerequisites and queries consist of pairs of distinct integers.

Hints

1. Graph Reachability:
   Think of the courses as nodes in a directed graph. A prerequisite relationship means there is a directed edge from one course to another. The problem then becomes checking if there is a path from one node to another.

2. Transitive Closure:
   Consider using algorithms that compute the transitive closure of the graph. With the constraints provided (n ≤ 100), methods like the Floyd–Warshall algorithm or DFS from each node are both viable.

Approach Overview

There are several ways to solve this problem. Let’s discuss two common approaches:

1. DFS (Depth-First Search) Approach

• Idea:
  For each course, perform a DFS (or BFS) to mark all courses that can be reached from it. Store this reachability information in a data structure (e.g., a 2D boolean array) so that each query can be answered in O(1) time.

• Steps:

  • Build an adjacency list from the prerequisite pairs.
  • For each course i (from 0 to n - 1), run a DFS/BFS to find all courses reachable from i and mark them.
  • For each query [u, v], simply return the stored reachability result for whether v is reachable from u.

• Time Complexity:
  O(n * (n + e)), where n is the number of courses and e is the number of edges (prerequisites).

• Space Complexity:
  O(n²) for storing the reachability matrix.

2. Floyd–Warshall Algorithm Approach

• Idea:
  Use the Floyd–Warshall algorithm to compute the transitive closure of the graph. Create a 2D boolean matrix reachable where reachable[i][j] is true if there is a path from course i to course j.

• Steps:

  • Initialize a matrix reachable of size n x n with false.
  • For each direct prerequisite [u, v], set reachable[u][v] = true.
  • For every intermediate course k from 0 to n - 1, update the matrix so that if reachable[i][k] and reachable[k][j] are both true, then reachable[i][j] becomes true.
  • Answer each query by returning the value in the reachable matrix.

• Time Complexity:
  O(n³), which is acceptable for n up to 100.

• Space Complexity:
  O(n²).

Code Implementation

Python Code