Course Schedule

Published at25 Jul 2026

Graph DFS Medium 0 views

Like0

There are n courses labeled from 0 to n-1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Determine if it is possible to finish all courses (i.e., check if the graph has no cycles).

Use DFS with three-state coloring: 0 = unvisited, 1 = visiting (currently on recursion stack), 2 = visited (fully processed). For each course, run DFS. If we encounter a node that is currently in the visiting state (state 1), a cycle exists and we return false. If a node is already fully processed (state 2), skip it.

This approach is efficient because each node is processed once in the main loop and the DFS visits each edge once. The three-state coloring is essential to detect back edges (cycles) in a directed graph.

Time complexity is O(V + E) where V is the number of courses and E is the number of prerequisites. Space complexity is O(V) for the visited array and recursion stack. The adjacency list is built from the prerequisites for efficient neighbor lookup.

Edge cases include no prerequisites (return true), a single course (return true), and various cycle configurations including self-loops (course requires itself, which is a cycle).

Example Input & Output

Example 1

Input

4,[[1,0],[2,1],[3,2]]

Output

true

Explanation

Linear chain, can finish

Example 2

Input

1,[]

Output

true

Explanation

Single course with no prerequisites

Example 3

Input

2,[[1,0],[0,1]]

Output

false

Explanation

Cycle: 0 needs 1, 1 needs 0, impossible

Example 4

Input

2,[[1,0]]

Output

true

Explanation

Course 1 has prerequisite 0, can finish

Example 5

Input

3,[[0,1],[1,2],[2,0]]

Output

false

Explanation

Triangle cycle

Algorithm Flow

Recommendation Algorithm Flow for Course Schedule

Solution Approach

Determine if it is possible to finish all courses given prerequisite pairs using topological sort (Kahn's algorithm). Build an adjacency list and an in-degree array. Courses with in-degree 0 have no prerequisites and can be taken first. Process them in a queue, reducing the in-degree of their dependents. If all courses are processed, no cycle exists.

function canFinish(numCourses, prerequisites) {
  var inDegree = Array(numCourses).fill(0);
  var adj = Array(numCourses).fill(null).map(function() { return []; });
  for (var i = 0; i < prerequisites.length; i++) {
    var course = prerequisites[i][0], prereq = prerequisites[i][1];
    adj[prereq].push(course);
    inDegree[course]++;
  }
  var queue = [];
  for (var i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  var taken = 0;
  while (queue.length) {
    var course = queue.shift();
    taken++;
    for (var i = 0; i < adj[course].length; i++) {
      inDegree[adj[course][i]]--;
      if (inDegree[adj[course][i]] === 0) queue.push(adj[course][i]);
    }
  }
  return taken === numCourses;
}

A cycle in the prerequisite graph makes it impossible to finish all courses because courses in the cycle would never have their in-degree reach 0. Kahn's algorithm detects this: if the number of processed courses is less than the total, a cycle exists.

Time complexity is O(V + E), space complexity is O(V + E).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public boolean solution(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        for (int[] p : prerequisites) adj[p[0]].add(p[1]);
        int[] visit = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, adj, visit)) return false;
        }
        return true;
    }
    boolean dfs(int u, List<Integer>[] adj, int[] visit) {
        if (visit[u] == 1) return false;
        if (visit[u] == 2) return true;
        visit[u] = 1;
        for (int v : adj[u]) { if (!dfs(v, adj, visit)) return false; }
        visit[u] = 2;
        return true;
    }
}

javascript

function solution(numCourses, prerequisites) {
  var adj = [];
  for (var i = 0; i < numCourses; i++) adj[i] = [];
  for (var i = 0; i < prerequisites.length; i++) {
    adj[prerequisites[i][0]].push(prerequisites[i][1]);
  }
  var visit = [];
  for (var i = 0; i < numCourses; i++) visit[i] = 0;
  function dfs(u) {
    if (visit[u] === 1) return false;
    if (visit[u] === 2) return true;
    visit[u] = 1;
    for (var i = 0; i < adj[u].length; i++) {
      if (!dfs(adj[u][i])) return false;
    }
    visit[u] = 2;
    return true;
  }
  for (var i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

php

<?php
function solution($numCourses, $prerequisites) {
    $adj = array_fill(0, $numCourses, []);
    foreach ($prerequisites as $p) $adj[$p[0]][] = $p[1];
    $visit = array_fill(0, $numCourses, 0);
    $dfs = function($u) use (&$dfs, $adj, &$visit) {
        if ($visit[$u] === 1) return false;
        if ($visit[$u] === 2) return true;
        $visit[$u] = 1;
        foreach ($adj[$u] as $v) { if (!$dfs($v)) return false; }
        $visit[$u] = 2;
        return true;
    };
    for ($i = 0; $i < $numCourses; $i++) { if (!$dfs($i)) return false; }
    return true;
}

python

def solution(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    for a, b in prerequisites: adj[a].append(b)
    visit = [0] * numCourses
    def dfs(u):
        if visit[u] == 1: return False
        if visit[u] == 2: return True
        visit[u] = 1
        for v in adj[u]:
            if not dfs(v): return False
        visit[u] = 2
        return True
    for i in range(numCourses):
        if not dfs(i): return False
    return True

rust

fn solution(numCourses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
    let n = numCourses as usize;
    let mut adj = vec![vec![]; n];
    for p in prerequisites { adj[p[0] as usize].push(p[1] as usize); }
    let mut visit = vec![0i32; n];
    fn dfs(u: usize, adj: &Vec<Vec<usize>>, visit: &mut Vec<i32>) -> bool {
        if visit[u] == 1 { return false; }
        if visit[u] == 2 { return true; }
        visit[u] = 1;
        for &v in &adj[u] { if !dfs(v, adj, visit) { return false; } }
        visit[u] = 2;
        true
    }
    for i in 0..n { if !dfs(i, &adj, &mut visit) { return false; } }
    true
}

typescript

function solution(numCourses: number, prerequisites: number[][]): boolean {
    var adj: number[][] = [];
    for (var i = 0; i < numCourses; i++) adj[i] = [];
    for (var i = 0; i < prerequisites.length; i++) {
        adj[prerequisites[i][0]].push(prerequisites[i][1]);
    }
    var visit: number[] = [];
    for (var i = 0; i < numCourses; i++) visit[i] = 0;
    function dfs(u: number): boolean {
        if (visit[u] === 1) return false;
        if (visit[u] === 2) return true;
        visit[u] = 1;
        for (var i = 0; i < adj[u].length; i++) {
            if (!dfs(adj[u][i])) return false;
        }
        visit[u] = 2;
        return true;
    }
    for (var i = 0; i < numCourses; i++) {
        if (!dfs(i)) return false;
    }
    return true;
}

Related Graph Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Course Schedule

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Graph Challenges

Garden Relay Count

Catalog Shelf Lineup

Ascending Manifest

Mountain Cabin Signal Range

Seaport Ferry Gate Control

City Bus Loop Access

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.