Topological sort

def topo_dfs(n, adj):
    colour = [0] * n                 # 0 white, 1 grey, 2 black
    finished = []
    def visit(u):
        colour[u] = 1
        for v in adj[u]:
            if colour[v] == 1:
                raise ValueError("cycle")
            if colour[v] == 0:
                visit(v)
        colour[u] = 2
        finished.append(u)           # u finishes after everything it points to
    for s in range(n):
        if colour[s] == 0:
            visit(s)
    return finished[::-1]

std::vector<int> topo_dfs(int n, const std::vector<std::vector<int>>& adj) {
    std::vector<int> colour(n, 0), finished;     // 0 white, 1 grey, 2 black
    std::function<void(int)> visit = [&](int u) {
        colour[u] = 1;
        for (int v : adj[u]) {
            if (colour[v] == 1) throw std::runtime_error("cycle");
            if (colour[v] == 0) visit(v);
        }
        colour[u] = 2;
        finished.push_back(u);                   // u finishes after everything it points to
    };
    for (int s = 0; s < n; ++s)
        if (colour[s] == 0) visit(s);
    std::reverse(finished.begin(), finished.end());
    return finished;
}

static List<Integer> topoDfs(int n, List<List<Integer>> adj) {
    int[] colour = new int[n];                   // 0 white, 1 grey, 2 black
    List<Integer> finished = new ArrayList<>();
    for (int s = 0; s < n; s++)
        if (colour[s] == 0) visit(s, adj, colour, finished);
    Collections.reverse(finished);
    return finished;
}

static void visit(int u, List<List<Integer>> adj, int[] colour, List<Integer> finished) {
    colour[u] = 1;
    for (int v : adj.get(u)) {
        if (colour[v] == 1) throw new IllegalStateException("cycle");
        if (colour[v] == 0) visit(v, adj, colour, finished);
    }
    colour[u] = 2;
    finished.add(u);                             // u finishes after everything it points to
}

function topoDfs(n, adj) {
    const colour = new Array(n).fill(0);         // 0 white, 1 grey, 2 black
    const finished = [];
    const visit = u => {
        colour[u] = 1;
        for (const v of adj[u]) {
            if (colour[v] === 1) throw new Error("cycle");
            if (colour[v] === 0) visit(v);
        }
        colour[u] = 2;
        finished.push(u);                        // u finishes after everything it points to
    };
    for (let s = 0; s < n; s++)
        if (colour[s] === 0) visit(s);
    return finished.reverse();
}

fn topo_dfs(n: usize, adj: &[Vec<usize>]) -> Result<Vec<usize>, &'static str> {
    fn visit(u: usize, adj: &[Vec<usize>], colour: &mut [u8], finished: &mut Vec<usize>) -> Result<(), &'static str> {
        colour[u] = 1;                           // 0 white, 1 grey, 2 black
        for &v in &adj[u] {
            if colour[v] == 1 { return Err("cycle"); }
            if colour[v] == 0 { visit(v, adj, colour, finished)?; }
        }
        colour[u] = 2;
        finished.push(u);                        // u finishes after everything it points to
        Ok(())
    }
    let (mut colour, mut finished) = (vec![0u8; n], Vec::new());
    for s in 0..n {
        if colour[s] == 0 { visit(s, adj, &mut colour, &mut finished)?; }
    }
    finished.reverse();
    Ok(finished)
}

topoDfs :: Int -> Array Int [Int] -> Maybe [Int]
topoDfs n adj = fst <$> foldM start ([], Map.empty) [0 .. n - 1]
  where
    -- colours: 0 white (absent), 1 grey, 2 black; Nothing means a cycle
    start st@(_, col) s = if Map.findWithDefault 0 s col == 0 then visit st s else Just st
    visit (fin, col) u = do
      (fin', col') <- foldM step (fin, Map.insert u 1 col) (adj ! u)
      Just (u : fin', Map.insert u 2 col')   -- u goes in front of everything it points to
    step st@(_, col) v = case Map.findWithDefault 0 v col of
      1 -> Nothing                           -- grey: a cycle
      0 -> visit st v
      _ -> Just st

import heapq

def course_order(n, prereqs):
    after = [[] for _ in range(n)]       # b -> courses that need b
    indeg = [0] * n
    for a, b in prereqs:
        after[b].append(a)
        indeg[a] += 1
    ready = [c for c in range(n) if indeg[c] == 0]
    heapq.heapify(ready)                 # smallest available course first
    order = []
    while ready:
        c = heapq.heappop(ready)
        order.append(c)
        for nxt in after[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                heapq.heappush(ready, nxt)
    return order if len(order) == n else []   # short: a cycle blocked the rest

#include <functional>
#include <queue>
#include <vector>

std::vector<int> solve(int n, const std::vector<std::vector<int>>& prereqs) {
    std::vector<std::vector<int>> after(n);
    std::vector<int> indeg(n, 0);
    for (const auto& p : prereqs) {
        after[p[1]].push_back(p[0]);
        ++indeg[p[0]];
    }
    std::priority_queue<int, std::vector<int>, std::greater<int>> ready;   // min-heap
    for (int c = 0; c < n; ++c) if (indeg[c] == 0) ready.push(c);
    std::vector<int> order;
    while (!ready.empty()) {
        int c = ready.top();
        ready.pop();
        order.push_back(c);
        for (int nxt : after[c]) if (--indeg[nxt] == 0) ready.push(nxt);
    }
    if ((int)order.size() < n) order.clear();   // a cycle blocked the rest
    return order;
}

import java.util.*;

class Solution {
    public int[] courseOrder(int n, int[][] prereqs) {
        List<List<Integer>> after = new ArrayList<>();
        for (int i = 0; i < n; i++) after.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : prereqs) {
            after.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        PriorityQueue<Integer> ready = new PriorityQueue<>();   // smallest first
        for (int c = 0; c < n; c++) if (indeg[c] == 0) ready.add(c);
        int[] order = new int[n];
        int k = 0;
        while (!ready.isEmpty()) {
            int c = ready.poll();
            order[k++] = c;
            for (int nxt : after.get(c)) if (--indeg[nxt] == 0) ready.add(nxt);
        }
        return k == n ? order : new int[0];     // short: a cycle blocked the rest
    }
}

function courseOrder(n, prereqs) {
  const after = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [a, b] of prereqs) { after[b].push(a); indeg[a]++; }
  // a binary min-heap of available courses
  const heap = [];
  const push = x => { heap.push(x); let i = heap.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (heap[p] <= heap[i]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
  const pop = () => { const top = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < heap.length && heap[l] < heap[m]) m = l; if (r < heap.length && heap[r] < heap[m]) m = r; if (m === i) break; [heap[m], heap[i]] = [heap[i], heap[m]]; i = m; } } return top; };
  for (let c = 0; c < n; c++) if (indeg[c] === 0) push(c);
  const order = [];
  while (heap.length) {
    const c = pop();
    order.push(c);
    for (const nxt of after[c]) if (--indeg[nxt] === 0) push(nxt);
  }
  return order.length === n ? order : [];   // short: a cycle blocked the rest
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn solve(n: i64, prereqs: &[[i64; 2]]) -> Vec<i64> {
    let n = n as usize;
    let mut after = vec![Vec::new(); n];
    let mut indeg = vec![0usize; n];
    for p in prereqs {
        after[p[1] as usize].push(p[0] as usize);
        indeg[p[0] as usize] += 1;
    }
    let mut ready: BinaryHeap<Reverse<usize>> = (0..n).filter(|&c| indeg[c] == 0).map(Reverse).collect();
    let mut order = Vec::with_capacity(n);
    while let Some(Reverse(c)) = ready.pop() {
        order.push(c as i64);
        for &nxt in &after[c] {
            indeg[nxt] -= 1;
            if indeg[nxt] == 0 {
                ready.push(Reverse(nxt));
            }
        }
    }
    if order.len() == n { order } else { Vec::new() }   // short: a cycle blocked the rest
}

import Data.List (foldl')
import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: Int -> [[Int]] -> [Int]
solve n prereqs = go ready0 indeg0 []
  where
    after = M.fromListWith (++) [(b, [a]) | [a, b] <- prereqs]
    indeg0 = M.fromListWith (+) [(a, 1 :: Int) | [a, _] <- prereqs]
    ready0 = S.fromList [c | c <- [0 .. n - 1], M.findWithDefault 0 c indeg0 == 0]
    -- the set is a min-heap: its smallest element is the next course
    go ready indeg acc = case S.minView ready of
      Nothing -> if length acc == n then reverse acc else []
      Just (c, rest) ->
        let (ready', indeg') = foldl' release (rest, indeg) (M.findWithDefault [] c after)
        in go ready' indeg' (c : acc)
    release (r, d) nxt =
      let k = M.findWithDefault 0 nxt d - 1
      in (if k == 0 then S.insert nxt r else r, M.insert nxt k d)