Data Structures
powered by pagefind esc close · ↑↓ navigate · ↵ open
practice · medium · from Graphs

Course Schedule (Topological Sort)

time
O(V + E)
space
O(V + E)
tags
graphs · topological-sort · cycle-detection

in the wild Build-system task ordering (make, bazel), package dependency resolution, ROS launch-file ordering, microservice startup choreography.

Problem

You're taking numCourses (labelled 0 through numCourses - 1). Each prerequisite is a pair [a, b] meaning "to take a, you must first take b". Return true if you can finish every course (i.e., the prerequisite graph has no cycle); otherwise false.

Examples

numCourses = 2,  prerequisites = [[1, 0]]
  → true     (take 0, then 1)

numCourses = 2,  prerequisites = [[1, 0], [0, 1]]
  → false    (cycle: 0 ↔ 1)

numCourses = 4,  prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
  → true     (0 → 1, 0 → 2, 1 → 3, 2 → 3 — a DAG)

numCourses = 3,  prerequisites = [[0, 1], [1, 2], [2, 0]]
  → false    (3-cycle)

Why this is the canonical "DAG / topological sort / cycle detection" problem

Three textbook graph concepts smashed together:

Two ways to solve, both O(V + E):

  1. Kahn's BFS algorithm. Compute in-degree of every node. Repeatedly pick an in-degree-0 node, "finish" it, and decrement in-degrees of its dependents. If you finish all numCourses, the graph is a DAG; if you stall first, there's a cycle.
  2. DFS with 3-color marking. Mark each node white/gray/black. Recurse from every white node; mark gray on entry, black on exit. Hitting a gray descendant = back edge = cycle.

Kahn's is more iterative-friendly and easier to extend to "give me the order"; the DFS version is shorter and makes cycle detection structurally obvious. Pick one; understand both.

This is the algorithm behind every build system, package manager, and "launch the services in dependency order" startup script you've ever used.

Hints

Hint 1 — model the problem as a graph

Each course is a node. The prerequisite [a, b] is what kind of edge? Directed or undirected? From which to which? Once you have the right graph, the question reduces to a classical one.

Hint 2 — the question, restated

"Can you finish all courses?" is equivalent to "does this directed graph have a cycle?". A schedule exists iff the graph is a DAG.

Hint 3 — Kahn's algorithm
compute indeg[v] for every v
queue = every v with indeg[v] == 0
finished = 0
while queue:
    u = queue.pop()
    finished += 1
    for v in graph[u]:
        indeg[v] -= 1
        if indeg[v] == 0: queue.push(v)
return finished == numCourses

If finished < numCourses at the end, the remaining nodes form a cycle.

Solution

from collections import deque, defaultdict

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    # Edge: b → a means "to take a, take b first". Build adjacency: out_edges[b] = [a, ...]
    graph: dict[int, list[int]] = defaultdict(list)
    indeg = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        indeg[a] += 1

    q: deque[int] = deque(v for v in range(num_courses) if indeg[v] == 0)
    finished = 0
    while q:
        u = q.popleft()
        finished += 1
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return finished == num_courses

cases = [
    (2, [[1, 0]],                       True),
    (2, [[1, 0], [0, 1]],               False),
    (4, [[1, 0], [2, 0], [3, 1], [3, 2]], True),
    (3, [[0, 1], [1, 2], [2, 0]],       False),
    (1, [],                              True),
]
for n, pre, expected in cases:
    got  = can_finish(n, pre)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} can_finish({n}, {pre}) = {got}  (expected {expected})")
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    indeg[a]++;
  }

  const q = [];
  for (let v = 0; v < numCourses; v++) if (indeg[v] === 0) q.push(v);
  let finished = 0, head = 0;
  while (head < q.length) {
    const u = q[head++];
    finished++;
    for (const v of graph[u]) {
      if (--indeg[v] === 0) q.push(v);
    }
  }
  return finished === numCourses;
}

const cases = [
  [2, [[1, 0]],                          true],
  [2, [[1, 0], [0, 1]],                  false],
  [4, [[1, 0], [2, 0], [3, 1], [3, 2]],  true],
  [3, [[0, 1], [1, 2], [2, 0]],          false],
  [1, [],                                 true],
];
for (const [n, pre, expected] of cases) {
  const got = canFinish(n, pre);
  console.log(`${got === expected ? "✓" : "✗"} canFinish(${n}, ${JSON.stringify(pre)}) = ${got}  (expected ${expected})`);
}
use std::collections::VecDeque;

pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
    let n = num_courses as usize;
    let mut graph: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut indeg: Vec<i32>        = vec![0; n];
    for p in prerequisites {
        let (a, b) = (p[0] as usize, p[1] as usize);
        graph[b].push(a);
        indeg[a] += 1;
    }

    let mut q: VecDeque<usize> = (0..n).filter(|&v| indeg[v] == 0).collect();
    let mut finished = 0;
    while let Some(u) = q.pop_front() {
        finished += 1;
        for &v in &graph[u] {
            indeg[v] -= 1;
            if indeg[v] == 0 { q.push_back(v); }
        }
    }
    finished == n
}

fn main() {
    let cases: Vec<(i32, Vec<Vec<i32>>, bool)> = vec![
        (2, vec![vec![1, 0]],                          true),
        (2, vec![vec![1, 0], vec![0, 1]],              false),
        (4, vec![vec![1, 0], vec![2, 0], vec![3, 1], vec![3, 2]], true),
        (3, vec![vec![0, 1], vec![1, 2], vec![2, 0]],  false),
        (1, vec![],                                     true),
    ];
    for (n, pre, expected) in cases {
        let got  = can_finish(n, pre.clone());
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} can_finish({}, {:?}) = {}  (expected {})", n, pre, got, expected);
    }
}
#include <iostream>
#include <queue>
#include <vector>

bool can_finish(int num_courses, std::vector<std::vector<int>>& prerequisites) {
    std::vector<std::vector<int>> graph(num_courses);
    std::vector<int>              indeg(num_courses, 0);
    for (auto& p : prerequisites) {
        graph[p[1]].push_back(p[0]);
        indeg[p[0]]++;
    }

    std::queue<int> q;
    for (int v = 0; v < num_courses; ++v) if (indeg[v] == 0) q.push(v);
    int finished = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ++finished;
        for (int v : graph[u]) if (--indeg[v] == 0) q.push(v);
    }
    return finished == num_courses;
}

int main() {
    struct Case { int n; std::vector<std::vector<int>> pre; bool expected; };
    std::vector<Case> cases = {
        {2, {{1, 0}},                                  true},
        {2, {{1, 0}, {0, 1}},                          false},
        {4, {{1, 0}, {2, 0}, {3, 1}, {3, 2}},          true},
        {3, {{0, 1}, {1, 2}, {2, 0}},                  false},
        {1, {},                                         true},
    };
    for (auto& c : cases) {
        bool got = can_finish(c.n, c.pre);
        std::cout << (got == c.expected ? "✓" : "✗")
                  << " can_finish(" << c.n << ", ...) = " << (got ? "true" : "false")
                  << "  (expected " << (c.expected ? "true" : "false") << ")\n";
    }
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool can_finish(int n, int (*pre)[2], int p_len) {
    int** graph    = malloc(n * sizeof(int*));
    int*  glen     = calloc(n,    sizeof(int));
    int*  gcap     = calloc(n,    sizeof(int));
    int*  indeg    = calloc(n,    sizeof(int));
    for (int i = 0; i < n; i++) graph[i] = NULL;

    for (int i = 0; i < p_len; i++) {
        int a = pre[i][0], b = pre[i][1];
        if (glen[b] == gcap[b]) {
            gcap[b] = gcap[b] ? gcap[b] * 2 : 4;
            graph[b] = realloc(graph[b], gcap[b] * sizeof(int));
        }
        graph[b][glen[b]++] = a;
        indeg[a]++;
    }

    int* q   = malloc(n * sizeof(int));
    int  head = 0, tail = 0;
    for (int v = 0; v < n; v++) if (indeg[v] == 0) q[tail++] = v;
    int finished = 0;
    while (head < tail) {
        int u = q[head++];
        finished++;
        for (int j = 0; j < glen[u]; j++) {
            int v = graph[u][j];
            if (--indeg[v] == 0) q[tail++] = v;
        }
    }

    for (int i = 0; i < n; i++) free(graph[i]);
    free(graph); free(glen); free(gcap); free(indeg); free(q);
    return finished == n;
}

int main(void) {
    int p1[][2] = {{1, 0}};
    int p2[][2] = {{1, 0}, {0, 1}};
    int p3[][2] = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
    int p4[][2] = {{0, 1}, {1, 2}, {2, 0}};
    printf("%s can_finish(2, p1) = %s  (expected true)\n",
           can_finish(2, p1, 1) ? "✓" : "✗", can_finish(2, p1, 1) ? "true" : "false");
    printf("%s can_finish(2, p2) = %s  (expected false)\n",
           !can_finish(2, p2, 2) ? "✓" : "✗", can_finish(2, p2, 2) ? "true" : "false");
    printf("%s can_finish(4, p3) = %s  (expected true)\n",
           can_finish(4, p3, 4) ? "✓" : "✗", can_finish(4, p3, 4) ? "true" : "false");
    printf("%s can_finish(3, p4) = %s  (expected false)\n",
           !can_finish(3, p4, 3) ? "✓" : "✗", can_finish(3, p4, 3) ? "true" : "false");
    return 0;
}

Five languages, one algorithm. The whole problem reduces to "do Kahn's BFS and check whether you visited every node" — exactly four important lines, no matter the syntax around them.

Complexity

Time
O(V + E) — every node enqueued once; every edge relaxed once.
Space
O(V + E) — adjacency list + queue + in-degree array.
DFS variant
Same complexity. Use 3-coloring (white = unvisited, gray = in DFS stack, black = done). Hitting a gray descendant = cycle.

In the wild

Variations