Course schedule

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

50.9% acceptance

Jan 12, 2026

17856

864

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 bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
    let n = num_courses as usize;
    let mut graph = vec![vec![]; n];
    
    for prereq in prerequisites {
      graph[prereq[1] as usize].push(prereq[0] as usize);
    }
    
    let mut visited = vec![0; n]; // 0: unvisited, 1: visiting, 2: visited
    
    for i in 0..n {
      if visited[i] == 0 && !Self::dfs(&graph, &mut visited, i) {
        return false;
      }
    }
    true
  }
  
  fn dfs(graph: &[Vec<usize>], visited: &mut [i32], node: usize) -> bool {
    visited[node] = 1;
    for &neighbor in &graph[node] {
      if visited[neighbor] == 1 { return false; }
      if visited[neighbor] == 0 && !Self::dfs(graph, visited, neighbor) {
        return false;
      }
    }
    visited[node] = 2;
    true
  }
}