Course Schedule
Determine whether all courses can be finished given prerequisites.
Pattern fit
This is a DAG / cycle-detection problem disguised as prerequisites, so either DFS coloring or BFS indegree processing is appropriate.
Key observation
The answer is no exactly when the directed graph contains a cycle.
Target complexity
O(V + E) / O(V + E)
How to break down the solution cleanly
This is a DAG / cycle-detection problem disguised as prerequisites, so either DFS coloring or BFS indegree processing is appropriate.
The answer is no exactly when the directed graph contains a cycle.
Identify the graph model and how neighbors are generated.
Choose BFS for shortest unweighted distance or DFS for structure exploration.
Reference implementation
Python# Generic pattern template
from collections import deque
def bfs(start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
def dfs(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(nxt)
Common pitfalls
Using visited alone and forgetting the need to distinguish the current recursion stack.
Confusing indegree-zero processing with simple BFS traversal.
Common follow-ups
How would you return one valid course order?
Why does indegree BFS prove acyclicity?
Continue with related problems
Build repeatable depth inside the BFS / DFS cluster before moving on.