AlgoViz
HomeGraphs

Course Schedule

Medium

Can you finish? = is it a DAG (no cycle)?

In simple words

You can finish all the courses only if their prerequisites don't form a loop.

The idea

Courses with prerequisites form a directed graph; you can finish everything exactly when there's no cycle. Kahn's algorithm peels off zero-prerequisite courses until none remain.

0123
indegrees[0,1,2,1]

Step 1 of 6. Kahn's algorithm: repeatedly take a course with 0 remaining prerequisites. indegrees [0,1,2,1].

1/6
Optimal
timeO(V+E)spaceO(V+E)

Cycle ⇒ impossible.

1q = every course whose indegree is 02while q not empty:3  c = q.pop(); processed += 14  for nb in adj[c]: indeg[nb] -= 1; if now 0, q.push(nb)5return processed == numCourses

Input

nodes
4, 4 edges

Memory

indegrees
[0,1,2,1]
processed
—

Output

finish
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
n = 2, prerequisites = [[1,0]]
Output:
true
Explanation:
Take 0 then 1 — no deadlock.

Example 2

Input:
n = 2, prerequisites = [[1,0],[0,1]]
Output:
false
Explanation:
They need each other → impossible.

Example 3

Input:
n = 3, prerequisites = [[1,0],[2,1]]
Output:
true
Explanation:
A clean chain works.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.