Course Schedule

medium graph topological sort cycle detection

Problem

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.

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;
}

Explanation

We only need a yes/no: can all courses be finished? They can exactly when the prerequisite graph has no cycle. The code checks this with Kahn's algorithm, counting how many courses we manage to "take".

Each prerequisite [a, b] becomes an edge b → a, and indeg[a] counts how many prerequisites still block course a. Every course with indeg == 0 can be taken now, so we seed the queue with them.

We then repeatedly pop a course, increment done, and decrease the in-degree of each course that depended on it. Whenever a course's count hits zero, it becomes available and joins the queue.

Example: n=4, prereqs=[[1,0],[2,1],[3,2]] forms a chain 0 → 1 → 2 → 3. We take 0, which frees 1, then 2, then 3. All four are taken, so the answer is true.

If a cycle existed, the courses inside it would never reach indeg 0 and never get dequeued. So at the end we simply return done == n: if every course was processed, there was no cycle.

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