Course Schedule
Hard · rating 1800 · Graphs
The first line has n (courses 0..n-1) and m (prerequisites). Each of the next m lines has a b, meaning course a requires course b first. Print YES if every course can be finished (no cyclic dependency), else NO.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Model courses as a directed graph (prerequisite → course). You can finish everything iff the graph has no cycle, which a topological sort (Kahn's algorithm) detects: repeatedly remove nodes with no remaining prerequisites. If every node comes off, there's no cycle.
Why leftovers mean a cycle
Any node still holding a positive in-degree at the end is stuck in a mutual dependency — a cycle — so not all courses can be ordered.
q = [i for i in range(n) if indeg[i] == 0]; done = 0
while q:
u = q.pop(); done += 1
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return done == nComplexity
Time: O(n + m). Space: O(n + m).
Related problems
- Shortest Grid Path — Hard
- Count Islands — Hard
- Max Area of Island — Hard