Course Schedule I and II
Model course prerequisites as a directed graph and use topological sort to determine if all courses can be completed and in which order.
Problem Overview
Course Schedule I (LeetCode 207): given n courses and a list of prerequisites pairs [a, b] meaning 'b must be taken before a', determine if you can finish all courses. Course Schedule II (LeetCode 210): return the actual order to take courses, or an empty array if impossible. Both reduce to topological sort on a directed graph where prerequisites are edges.
Graph Modelling
Build a directed graph: for each prerequisite pair [a, b], add edge b → a ('b must come before a' means b leads to a). Compute in-degrees for each course. A course with in-degree 0 has no prerequisites and can be taken immediately. The problem is solvable if and only if no cycle exists in this graph (no circular dependency).
from collections import defaultdict
def build_graph(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for a, b in prerequisites: # b must come before a
graph[b].append(a)
in_degree[a] += 1
return graph, in_degree
graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind) # [0, 1, 1, 2]
print('Graph edges:', dict(graph))