Depth-first cycle check
StopGraph
- CH4 path
11/11
Mark the courses on the current path. An edge back to one of them is a cycle.
Step through it →Topological Sort
A topological sort orders tasks so each comes after everything it needs, by taking whatever nothing still blocks. Whatever is never taken sits on a cycle.
Course schedule: take what nothing blocks
StopGraph
prerequisites
4 courses, every in-degree 0. Now read the pairs, one edge at a time.
Typical cost O(V + E) time, O(V) spaceFull lesson: Course Schedule →
When to reach for it
- Tasks depend on other tasks: prerequisites, build steps, imports.
- You need an order that respects every dependency.
- You need to know whether a cycle makes any order impossible.
- The input is a directed graph, often given as pairs.
What stays true
A course's in-degree counts the prerequisites not yet taken. It drops by one as each is taken, and the course is queued when it reaches 0, just after the last one.
Nothing is taken before what it needs
StopGraph
InvariantA course joins the queue only once every course it needs is taken.✓ Holds
6 courses, every in-degree 0. Now read the pairs, one edge at a time.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Course 0 is taken, then the queue runs dry with 1, 2 and 3 left. Checking only that the queue started non-empty would answer True.
Course schedule on the inputs that trip it up
StopGraph
4 courses, every in-degree 0. Now read the pairs, one edge at a time.
AnswerfalseSteps10
Variants
The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Course schedule: take what nothing blocks
StopGraph
4 courses, every in-degree 0. Now read the pairs, one edge at a time.
course_schedule.py
from collections import dequedef can_finish(num_courses, prerequisites): graph = [[] for _ in range(num_courses)] indegree = [0] * num_courses for course, prereq in prerequisites: graph[prereq].append(course) indegree[course] += 1 queue = deque(c for c in range(num_courses) if indegree[c] == 0) order = [] while queue: course = queue.popleft() order.append(course) for nxt in graph[course]: indegree[nxt] -= 1 if indegree[nxt] == 0: queue.append(nxt) return len(order) == num_coursesDrill it
Course ScheduleRuns live,Medium
Course Schedule IIMedium
Alien DictionaryHard
Minimum Height TreesMedium