Are Course Prerequisites Satisfiable

medium graph topological sort cycle detection

Problem

Given n courses and a list of pairs [a, b] meaning "to take a, finish b first", decide whether you can finish every course.

Treat each pair as a directed edge b → a. The schedule is feasible iff this DAG has no cycle. Kahn's algorithm: compute in-degree for every course, push every zero-in-degree course onto a queue, then repeatedly pop a course and decrement in-degrees of its successors, queuing any that hit zero. If the dequeue count equals n, the graph is acyclic.

Inputn = 4, prereqs = [[1,0],[2,1],[3,2]]

Outputtrue

Linear chain 0 → 1 → 2 → 3, no cycles. Adding [0,3] would close a cycle and fail.

prereqs (e.g. "1,0; 2,1; 3,2")

from collections import deque
def can_finish(n, prereqs):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in prereqs:
        g[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft(); done += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return done == n

function canFinish(n, prereqs) {
  const g = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [a, b] of prereqs) { g[b].push(a); indeg[a]++; }
  const q = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  let done = 0;
  while (q.length) {
    const u = q.shift(); done++;
    for (const v of g[u]) if (--indeg[v] === 0) q.push(v);
  }
  return done === n;
}

class Solution {
    public boolean canFinish(int n, int[][] prereqs) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] e : prereqs) { g.get(e[1]).add(e[0]); indeg[e[0]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
        int done = 0;
        while (!q.isEmpty()) {
            int u = q.poll(); done++;
            for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
        }
        return done == n;
    }
}

bool canFinish(int n, vector<vector<int>>& prereqs) {
    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);
    for (auto& e : prereqs) { g[e[1]].push_back(e[0]); indeg[e[0]]++; }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    int done = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); done++;
        for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
    }
    return done == n;
}

Time: O(V + E) Space: O(V + E)