#4 · Graphs

Course Schedule

There are n courses, and prerequisites[i] = [a, b] means you must take b before a. Return true if you can finish all courses, which is the same as asking whether the prerequisite graph has no cycle.

MediumLeetCode

Current
On path / queued
Done
Cycle / blocked

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Directed graph as an adjacency list

Each course maps to the list of courses that depend on it (edge pre → course). The question "can all courses be finished" is exactly "is this directed graph acyclic (a DAG)?".

Memory layout

An array of n lists (O(V + E) total). Each list is a separate heap allocation, so scanning a node's neighbours is contiguous but hopping between nodes is pointer-chasing. A CSR layout flattens everything into two arrays.

Operation	Cost
build	O(V + E)
iterate neighbours of u	O(out-degree(u))
edge existence test	O(out-degree) (use a set if needed)

Indegree array + queue (or colour array + stack)

Two ways to prove acyclicity: Kahn's algorithm repeatedly removes nodes with no unmet prerequisites; DFS with three colours looks for a back edge to a node still on the stack.

Memory layout

Kahn: an int[n] of indegrees and a queue of at most n entries. DFS: an int[n] of states plus a recursion stack up to depth n.

Operation	Cost
Kahn total	O(V + E) time, O(V) extra space
DFS total	O(V + E) time, O(V) stack + state

Why it fits

A valid course order exists iff the graph has a topological order, which exists iff there is no directed cycle. So the problem is pure cycle detection.
Both linear algorithms share one idea: never expand a node twice. Kahn does it via indegrees; DFS does it via the DONE colour.
Kahn's also yields the actual order (Course Schedule II) for free, and its iterative form has no recursion-depth limit.

Why alternatives degrade

DFS from every node without memoization:: Re-explores shared sub-DAGs; on a DAG with diamonds it can take exponential time.
Adjacency matrix:: O(V²) memory and O(V) neighbour scans: wasteful for sparse prerequisite graphs.
Union-Find:: Detects cycles in undirected graphs; direction matters here (A→B→C is fine, A→B, C→B is fine too), so union-find would give false positives.

Four approaches, from naive to production

1 · beginner

DFS from every start (path set only)

time O(V · 2^V) worst case, O(V · (V + E)) on easy inputsspace O(V) path + recursion

For each course, DFS along prerequisites keeping the current path in a set; if we reach a node already on the path, there is a cycle.

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    for (auto& p : prerequisites) adj[p[1]].push_back(p[0]);
    unordered_set<int> path;
    function<bool(int)> hasCycleFrom = [&](int node) -> bool {
        if (path.count(node)) return true;
        path.insert(node);
        for (int next : adj[node]) {
            if (hasCycleFrom(next)) return true;
        }
        path.erase(node);
        return false;
    };
    for (int c = 0; c < n; c++) {
        path.clear();
        if (hasCycleFrom(c)) return false;
    }
    return true;
}

public boolean canFinish(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
    for (int c = 0; c < n; c++) {
        if (hasCycleFrom(c, new HashSet<>(), adj)) return false;
    }
    return true;
}

private boolean hasCycleFrom(int node, Set<Integer> path, List<List<Integer>> adj) {
    if (path.contains(node)) return true;
    path.add(node);
    for (int next : adj.get(node)) {
        if (hasCycleFrom(next, path, adj)) return true;
    }
    path.remove(node);
    return false;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(n)]
    for course, pre in prerequisites: adj[pre].append(course)
    def has_cycle_from(node: int, path: set[int]) -> bool:
        if node in path: return True
        path.add(node)
        for nxt in adj[node]:
            if has_cycle_from(nxt, path): return True
        path.remove(node)
        return False
    for c in range(n):
        if has_cycle_from(c, set()): return False
    return True

function canFinish(n: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [course, pre] of prerequisites) adj[pre].push(course);
  const hasCycleFrom = (node: number, path: Set<number>): boolean => {
    if (path.has(node)) return true;
    path.add(node);
    for (const next of adj[node]) {
      if (hasCycleFrom(next, path)) return true;
    }
    path.delete(node);
    return false;
  };
  for (let c = 0; c < n; c++) {
    if (hasCycleFrom(c, new Set())) return false;
  }
  return true;
}

Flaws & bottlenecks

No memo: a node reachable by many paths is re-explored each time. A chain of diamonds makes this exponential.
Restarts a fresh DFS from every node, repeating work already done from earlier starts.
Recursion depth up to V can overflow the stack on a long prerequisite chain.

Interviewer cross-questions

What exactly is wasted here?

Say: Once a DFS from some node finishes without finding a cycle, everything it reached is proven cycle-free, yet the next start re-walks it. Remembering that result (a DONE state) removes all repeated exploration.

Why is a path set correct but a plain visited set is not?

Say: Reaching an already-visited node is only a cycle if it is an ancestor on the current path. In a diamond (A→B, A→C, B→D, C→D), D is visited twice with no cycle. The path set distinguishes ancestor from merely-seen.

Give an input that makes it exponential.

Say: A chain of k diamonds: each diamond doubles the number of distinct paths to the end, so the DFS makes 2^k visits to the last node. The memoized version visits each node once.

2 · intermediate

DFS with three states (new / visiting / done)

time O(V + E)space O(V + E)

Colour nodes white (new), gray (on the DFS stack) and black (finished). A cycle exists exactly when DFS meets a gray node.

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    for (auto& p : prerequisites) adj[p[1]].push_back(p[0]);
    vector<int> state(n, 0); // 0 = new, 1 = visiting, 2 = done
    function<bool(int)> hasCycle = [&](int u) -> bool {
        if (state[u] == 1) return true;
        if (state[u] == 2) return false;
        state[u] = 1;
        for (int v : adj[u]) if (hasCycle(v)) return true;
        state[u] = 2;
        return false;
    };
    for (int u = 0; u < n; u++) if (hasCycle(u)) return false;
    return true;
}

public boolean canFinish(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
    int[] state = new int[n]; // 0 = new, 1 = visiting, 2 = done
    for (int u = 0; u < n; u++) if (hasCycle(u, adj, state)) return false;
    return true;
}

private boolean hasCycle(int u, List<List<Integer>> adj, int[] state) {
    if (state[u] == 1) return true;
    if (state[u] == 2) return false;
    state[u] = 1;
    for (int v : adj.get(u)) if (hasCycle(v, adj, state)) return true;
    state[u] = 2;
    return false;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(n)]
    for course, pre in prerequisites: adj[pre].append(course)
    state = [0] * n  # 0 = new, 1 = visiting, 2 = done
    def has_cycle(u: int) -> bool:
        if state[u] == 1: return True
        if state[u] == 2: return False
        state[u] = 1
        for v in adj[u]:
            if has_cycle(v): return True
        state[u] = 2
        return False
    for u in range(n):
        if has_cycle(u): return False
    return True

function canFinish(n: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [course, pre] of prerequisites) adj[pre].push(course);
  const state = new Array<number>(n).fill(0); // 0 = new, 1 = visiting, 2 = done
  const hasCycle = (u: number): boolean => {
    if (state[u] === 1) return true;
    if (state[u] === 2) return false;
    state[u] = 1;
    for (const v of adj[u]) if (hasCycle(v)) return true;
    state[u] = 2;
    return false;
  };
  for (let u = 0; u < n; u++) if (hasCycle(u)) return false;
  return true;
}

Flaws & bottlenecks

Recursive: a prerequisite chain of 10⁵ courses overflows the call stack in most runtimes.
Only answers yes/no; recovering the cycle (or an ordering) needs extra bookkeeping such as parent pointers or a post-order list.
Needs a separate state array on top of the adjacency list.

Interviewer cross-questions

Why do you need three states instead of a boolean visited?

Say: Two bits of information are needed: "seen at all" (to avoid redoing work) and "currently on the stack" (to recognize a back edge). Gray means on the stack and black means finished; meeting black is harmless, meeting gray is a cycle.

How do you make it iterative?

Say: Use an explicit stack of (node, next-neighbour-index) frames, set state on push/pop exactly where the recursion would, and the algorithm is unchanged but limited by heap memory, not call-stack depth.

Can you also return a valid course order?

Say: Yes: append each node to a list when it turns black. The reverse of that post-order is a topological order (that is Course Schedule II).

3 · advanced

Kahn's algorithm (BFS topological sort)

time O(V + E)space O(V + E)

Repeatedly take any course whose prerequisites are all satisfied (indegree 0). If every course gets taken there is no cycle.

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    vector<int> indegree(n, 0);
    for (auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        indegree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);
    int taken = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        taken++;
        for (int v : adj[u]) {
            if (--indegree[v] == 0) q.push(v);
        }
    }
    return taken == n;
}

public boolean canFinish(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[n];
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.add(i);
    int taken = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        taken++;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) queue.add(v);
        }
    }
    return taken == n;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for course, pre in prerequisites:
        adj[pre].append(course)
        indegree[course] += 1
    queue = deque()
    for i in range(n):
        if indegree[i] == 0: queue.append(i)
    taken = 0
    while queue:
        u = queue.popleft()
        taken += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0: queue.append(v)
    return taken == n

function canFinish(n: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  const indegree = new Array<number>(n).fill(0);
  for (const [course, pre] of prerequisites) {
    adj[pre].push(course);
    indegree[course]++;
  }
  const queue: number[] = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
  let taken = 0;
  while (queue.length > 0) {
    const u = queue.shift()!;
    taken++;
    for (const v of adj[u]) {
      if (--indegree[v] === 0) queue.push(v);
    }
  }
  return taken === n;
}

Flaws & bottlenecks

Array.shift() is O(n) on large arrays in many engines, which can degrade the loop to O(V²).
Builds one array object per node, which is memory-heavy and cache-unfriendly for large sparse graphs.
Tells you a cycle exists but not which nodes form it (only that some nodes were never freed).

Interviewer cross-questions

Why does leftover nonzero indegree prove a cycle?

Say: A node that is never dequeued still has an unmet prerequisite, and that prerequisite is itself never dequeued. Following unmet prerequisites backwards among the remaining nodes must eventually revisit a node, since the set is finite, which gives a cycle.

BFS or DFS, which would you pick in production?

Say: Kahn's. It is iterative (no stack overflow), naturally produces an order, can process a level of independent courses in parallel, and its leftover set pinpoints the stuck nodes.

How do you run it on a graph that doesn't fit in memory?

Say: Stream the edges once to count indegrees, keep only the indegree array and the queue in memory, and re-stream the edge list (sorted or partitioned by source) when a node is dequeued. That costs more I/O passes but only O(V) memory.

4 · expert

Kahn on flat CSR arrays with validation

time O(V + E)space O(V + E), 4 flat Int32 arrays

Same algorithm, but the graph is stored in compressed-sparse-row form (two Int32Arrays), the queue is a plain Int32Array with head and tail indices, and input is validated up front.

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    if (n <= 0) return true;
    int m = prerequisites.size();
    vector<int> head(n + 1, 0);
    vector<int> indegree(n, 0);
    for (int i = 0; i < m; i++) {
        int course = prerequisites[i][0], pre = prerequisites[i][1];
        if (course < 0 || course >= n || pre < 0 || pre >= n) return false;
        head[pre + 1]++;
        indegree[course]++;
    }
    for (int i = 0; i < n; i++) head[i + 1] += head[i];
    vector<int> to(m);
    vector<int> fill(head.begin(), head.begin() + n);
    for (int i = 0; i < m; i++) to[fill[prerequisites[i][1]]++] = prerequisites[i][0];
    vector<int> queue(n);
    int qh = 0, qt = 0;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue[qt++] = i;
    while (qh < qt) {
        int u = queue[qh++];
        for (int e = head[u]; e < head[u + 1]; e++) {
            if (--indegree[to[e]] == 0) queue[qt++] = to[e];
        }
    }
    return qt == n;
}

public boolean canFinish(int n, int[][] prerequisites) {
    if (n <= 0) return true;
    int m = prerequisites.length;
    int[] head = new int[n + 1];
    int[] indegree = new int[n];
    for (int i = 0; i < m; i++) {
        int course = prerequisites[i][0], pre = prerequisites[i][1];
        if (course < 0 || course >= n || pre < 0 || pre >= n) return false;
        head[pre + 1]++;
        indegree[course]++;
    }
    for (int i = 0; i < n; i++) head[i + 1] += head[i];
    int[] to = new int[m];
    int[] fill = Arrays.copyOf(head, n);
    for (int i = 0; i < m; i++) to[fill[prerequisites[i][1]]++] = prerequisites[i][0];
    int[] queue = new int[n];
    int qh = 0, qt = 0;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue[qt++] = i;
    while (qh < qt) {
        int u = queue[qh++];
        for (int e = head[u]; e < head[u + 1]; e++) {
            if (--indegree[to[e]] == 0) queue[qt++] = to[e];
        }
    }
    return qt == n;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    if n <= 0: return True
    m = len(prerequisites)
    head = [0] * (n + 1)
    indegree = [0] * n
    for i in range(m):
        course, pre = prerequisites[i]
        if not (0 <= course < n and 0 <= pre < n): return False
        head[pre + 1] += 1
        indegree[course] += 1
    for i in range(n): head[i + 1] += head[i]
    to = [0] * m
    fill = head[:n]
    for i in range(m):
        to[fill[prerequisites[i][1]]] = prerequisites[i][0]
        fill[prerequisites[i][1]] += 1
    queue = [0] * n
    qh = qt = 0
    for i in range(n):
        if indegree[i] == 0:
            queue[qt] = i
            qt += 1
    while qh < qt:
        u = queue[qh]
        qh += 1
        for e in range(head[u], head[u + 1]):
            indegree[to[e]] -= 1
            if indegree[to[e]] == 0:
                queue[qt] = to[e]
                qt += 1
    return qt == n

function canFinish(n: number, prerequisites: number[][]): boolean {
  if (n <= 0) return true;
  const m = prerequisites.length;
  const head = new Int32Array(n + 1);
  const indegree = new Int32Array(n);
  for (let i = 0; i < m; i++) {
    const [course, pre] = prerequisites[i];
    if (course < 0 || course >= n || pre < 0 || pre >= n) return false;
    head[pre + 1]++;
    indegree[course]++;
  }
  for (let i = 0; i < n; i++) head[i + 1] += head[i];
  const to = new Int32Array(m);
  const fill = head.slice(0, n);
  for (let i = 0; i < m; i++) to[fill[prerequisites[i][1]]++] = prerequisites[i][0];
  const queue = new Int32Array(n);
  let qh = 0, qt = 0;
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue[qt++] = i;
  while (qh < qt) {
    const u = queue[qh++];
    for (let e = head[u]; e < head[u + 1]; e++) {
      if (--indegree[to[e]] === 0) queue[qt++] = to[e];
    }
  }
  return qt === n;
}

Flaws & bottlenecks

Considerably more code than the list version, with off-by-one risk in the prefix sums and scatter pass.
Needs two passes over the edge list (count, then scatter), so edges must be re-readable, not a one-shot stream.
Int32 limits V and E to ~2³¹; larger graphs need 64-bit offsets.

Interviewer cross-questions

Why CSR instead of an array of arrays?

Say: Neighbours of a node are one contiguous slice, so scans are cache- and prefetch-friendly. There is no per-node allocation (so no GC pressure and no 16+ byte object headers), and the whole graph is two flat buffers that can even be memory-mapped or shared between workers.

Why validate bounds up front?

Say: A bad edge like [7, 2] with n = 5 would write out of range in a typed array (silently ignored in JS) or corrupt memory in C++. Failing fast keeps the invariants the rest of the loop relies on.

How would you parallelize this?

Say: Process the queue in waves: all nodes at indegree 0 are independent, so each wave's dequeues can run on separate threads, with atomic decrements on indegree[to[e]]. A node is enqueued by whichever thread drives its counter to zero.

Synchronized code walkthrough

Showing: DFS from every start (path set only) — shares the player above; click any step to jump.

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    for (auto& p : prerequisites) adj[p[1]].push_back(p[0]);
    unordered_set<int> path;
    function<bool(int)> hasCycleFrom = [&](int node) -> bool {
        if (path.count(node)) return true;
        path.insert(node);
        for (int next : adj[node]) {
            if (hasCycleFrom(next)) return true;
        }
        path.erase(node);
        return false;
    };
    for (int c = 0; c < n; c++) {
        path.clear();
        if (hasCycleFrom(c)) return false;
    }
    return true;
}

public boolean canFinish(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
    for (int c = 0; c < n; c++) {
        if (hasCycleFrom(c, new HashSet<>(), adj)) return false;
    }
    return true;
}

private boolean hasCycleFrom(int node, Set<Integer> path, List<List<Integer>> adj) {
    if (path.contains(node)) return true;
    path.add(node);
    for (int next : adj.get(node)) {
        if (hasCycleFrom(next, path, adj)) return true;
    }
    path.remove(node);
    return false;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(n)]
    for course, pre in prerequisites: adj[pre].append(course)
    def has_cycle_from(node: int, path: set[int]) -> bool:
        if node in path: return True
        path.add(node)
        for nxt in adj[node]:
            if has_cycle_from(nxt, path): return True
        path.remove(node)
        return False
    for c in range(n):
        if has_cycle_from(c, set()): return False
    return True

function canFinish(n: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [course, pre] of prerequisites) adj[pre].push(course);
  const hasCycleFrom = (node: number, path: Set<number>): boolean => {
    if (path.has(node)) return true;
    path.add(node);
    for (const next of adj[node]) {
      if (hasCycleFrom(next, path)) return true;
    }
    path.delete(node);
    return false;
  };
  for (let c = 0; c < n; c++) {
    if (hasCycleFrom(c, new Set())) return false;
  }
  return true;
}

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    for (auto& p : prerequisites) adj[p[1]].push_back(p[0]);
    vector<int> state(n, 0); // 0 = new, 1 = visiting, 2 = done
    function<bool(int)> hasCycle = [&](int u) -> bool {
        if (state[u] == 1) return true;
        if (state[u] == 2) return false;
        state[u] = 1;
        for (int v : adj[u]) if (hasCycle(v)) return true;
        state[u] = 2;
        return false;
    };
    for (int u = 0; u < n; u++) if (hasCycle(u)) return false;
    return true;
}

public boolean canFinish(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
    int[] state = new int[n]; // 0 = new, 1 = visiting, 2 = done
    for (int u = 0; u < n; u++) if (hasCycle(u, adj, state)) return false;
    return true;
}

private boolean hasCycle(int u, List<List<Integer>> adj, int[] state) {
    if (state[u] == 1) return true;
    if (state[u] == 2) return false;
    state[u] = 1;
    for (int v : adj.get(u)) if (hasCycle(v, adj, state)) return true;
    state[u] = 2;
    return false;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(n)]
    for course, pre in prerequisites: adj[pre].append(course)
    state = [0] * n  # 0 = new, 1 = visiting, 2 = done
    def has_cycle(u: int) -> bool:
        if state[u] == 1: return True
        if state[u] == 2: return False
        state[u] = 1
        for v in adj[u]:
            if has_cycle(v): return True
        state[u] = 2
        return False
    for u in range(n):
        if has_cycle(u): return False
    return True

function canFinish(n: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [course, pre] of prerequisites) adj[pre].push(course);
  const state = new Array<number>(n).fill(0); // 0 = new, 1 = visiting, 2 = done
  const hasCycle = (u: number): boolean => {
    if (state[u] === 1) return true;
    if (state[u] === 2) return false;
    state[u] = 1;
    for (const v of adj[u]) if (hasCycle(v)) return true;
    state[u] = 2;
    return false;
  };
  for (let u = 0; u < n; u++) if (hasCycle(u)) return false;
  return true;
}

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    vector<int> indegree(n, 0);
    for (auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        indegree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);
    int taken = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        taken++;
        for (int v : adj[u]) {
            if (--indegree[v] == 0) q.push(v);
        }
    }
    return taken == n;
}

public boolean canFinish(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[n];
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.add(i);
    int taken = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        taken++;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) queue.add(v);
        }
    }
    return taken == n;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for course, pre in prerequisites:
        adj[pre].append(course)
        indegree[course] += 1
    queue = deque()
    for i in range(n):
        if indegree[i] == 0: queue.append(i)
    taken = 0
    while queue:
        u = queue.popleft()
        taken += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0: queue.append(v)
    return taken == n

function canFinish(n: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  const indegree = new Array<number>(n).fill(0);
  for (const [course, pre] of prerequisites) {
    adj[pre].push(course);
    indegree[course]++;
  }
  const queue: number[] = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
  let taken = 0;
  while (queue.length > 0) {
    const u = queue.shift()!;
    taken++;
    for (const v of adj[u]) {
      if (--indegree[v] === 0) queue.push(v);
    }
  }
  return taken === n;
}

bool canFinish(int n, vector<vector<int>>& prerequisites) {
    if (n <= 0) return true;
    int m = prerequisites.size();
    vector<int> head(n + 1, 0);
    vector<int> indegree(n, 0);
    for (int i = 0; i < m; i++) {
        int course = prerequisites[i][0], pre = prerequisites[i][1];
        if (course < 0 || course >= n || pre < 0 || pre >= n) return false;
        head[pre + 1]++;
        indegree[course]++;
    }
    for (int i = 0; i < n; i++) head[i + 1] += head[i];
    vector<int> to(m);
    vector<int> fill(head.begin(), head.begin() + n);
    for (int i = 0; i < m; i++) to[fill[prerequisites[i][1]]++] = prerequisites[i][0];
    vector<int> queue(n);
    int qh = 0, qt = 0;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue[qt++] = i;
    while (qh < qt) {
        int u = queue[qh++];
        for (int e = head[u]; e < head[u + 1]; e++) {
            if (--indegree[to[e]] == 0) queue[qt++] = to[e];
        }
    }
    return qt == n;
}

public boolean canFinish(int n, int[][] prerequisites) {
    if (n <= 0) return true;
    int m = prerequisites.length;
    int[] head = new int[n + 1];
    int[] indegree = new int[n];
    for (int i = 0; i < m; i++) {
        int course = prerequisites[i][0], pre = prerequisites[i][1];
        if (course < 0 || course >= n || pre < 0 || pre >= n) return false;
        head[pre + 1]++;
        indegree[course]++;
    }
    for (int i = 0; i < n; i++) head[i + 1] += head[i];
    int[] to = new int[m];
    int[] fill = Arrays.copyOf(head, n);
    for (int i = 0; i < m; i++) to[fill[prerequisites[i][1]]++] = prerequisites[i][0];
    int[] queue = new int[n];
    int qh = 0, qt = 0;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue[qt++] = i;
    while (qh < qt) {
        int u = queue[qh++];
        for (int e = head[u]; e < head[u + 1]; e++) {
            if (--indegree[to[e]] == 0) queue[qt++] = to[e];
        }
    }
    return qt == n;
}

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    if n <= 0: return True
    m = len(prerequisites)
    head = [0] * (n + 1)
    indegree = [0] * n
    for i in range(m):
        course, pre = prerequisites[i]
        if not (0 <= course < n and 0 <= pre < n): return False
        head[pre + 1] += 1
        indegree[course] += 1
    for i in range(n): head[i + 1] += head[i]
    to = [0] * m
    fill = head[:n]
    for i in range(m):
        to[fill[prerequisites[i][1]]] = prerequisites[i][0]
        fill[prerequisites[i][1]] += 1
    queue = [0] * n
    qh = qt = 0
    for i in range(n):
        if indegree[i] == 0:
            queue[qt] = i
            qt += 1
    while qh < qt:
        u = queue[qh]
        qh += 1
        for e in range(head[u], head[u + 1]):
            indegree[to[e]] -= 1
            if indegree[to[e]] == 0:
                queue[qt] = to[e]
                qt += 1
    return qt == n

function canFinish(n: number, prerequisites: number[][]): boolean {
  if (n <= 0) return true;
  const m = prerequisites.length;
  const head = new Int32Array(n + 1);
  const indegree = new Int32Array(n);
  for (let i = 0; i < m; i++) {
    const [course, pre] = prerequisites[i];
    if (course < 0 || course >= n || pre < 0 || pre >= n) return false;
    head[pre + 1]++;
    indegree[course]++;
  }
  for (let i = 0; i < n; i++) head[i + 1] += head[i];
  const to = new Int32Array(m);
  const fill = head.slice(0, n);
  for (let i = 0; i < m; i++) to[fill[prerequisites[i][1]]++] = prerequisites[i][0];
  const queue = new Int32Array(n);
  let qh = 0, qt = 0;
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue[qt++] = i;
  while (qh < qt) {
    const u = queue[qh++];
    for (let e = head[u]; e < head[u + 1]; e++) {
      if (--indegree[to[e]] === 0) queue[qt++] = to[e];
    }
  }
  return qt === n;
}