Course schedule iv

Depth-First Search Breadth-First Search Graph Theory Topological Sort

59.7% acceptance

Feb 25, 2026

2116

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn check_if_prerequisite(num_courses: i32, prerequisites: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<bool> {
    let n = num_courses as usize;
    let mut reach = vec![vec![false; n]; n];
    for pre in &prerequisites {
      reach[pre[0] as usize][pre[1] as usize] = true;
    }
    // Floyd-Warshall transitive closure
    for k in 0..n {
      for i in 0..n {
        for j in 0..n {
          if reach[i][k] && reach[k][j] {
            reach[i][j] = true;
          }
        }
      }
    }
    queries.iter().map(|q| reach[q[0] as usize][q[1] as usize]).collect()
  }
}