AdvancedGraphs
Topological sort for dependencies
Take courses with no remaining prerequisites first, then unlock what depends on them. If some never unlock, there's a cycle.
The idea
When tasks depend on others, count each task's unmet prerequisites (its in-degree). Every task at 0 can start now. Finishing one lowers its dependents' counts; any that hit 0 can start next (Kahn's algorithm).
If you finish fewer tasks than exist, the rest are stuck in a cycle.
Worked example
4 courses: 1 needs 0, 2 needs 0, 3 needs 1 and 2
- In-degrees: 0:0, 1:1, 2:1, 3:2 → start with [0]
- Take 0 → 1 and 2 drop to 0 → take 1 → 3 drops to 1 → take 2 → 3 drops to 0 → take 3
- Order 0, 1, 2, 3; all 4 taken → possible.
In code (Python)
from collections import deque
def can_finish(num_courses, prerequisites):
needs = [0] * num_courses
unlocks = [[] for _ in range(num_courses)]
for course, pre in prerequisites:
needs[course] += 1
unlocks[pre].append(course)
ready = deque(c for c in range(num_courses) if needs[c] == 0)
taken = 0
while ready:
c = ready.popleft()
taken += 1
for nxt in unlocks[c]:
needs[nxt] -= 1
if needs[nxt] == 0:
ready.append(nxt)
return taken == num_coursesO(V + E) time and space.
How to spot it
- Prerequisites, build order, “is there a valid order”, detecting cycles in a directed graph.
Common mistakes
- Building edges backwards (pre → course is what unlocks).
- Forgetting that a cycle means some in-degrees never reach 0.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →