Course Schedule

An example of cycle-detection in graph.

Approach 1: Topological Sort with Kahn’s Algorithm

indegs = [0] * numCourses
adj = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
    indegs[course] += 1
    adj[prereq].append(course)
queue = deque([
    course for course, indeg in enumerate(indegs) if not indeg
])
 
taken = 0
while queue:
    prereq = queue.popleft()  # no prereq required, take this!
    taken += 1
    for course in adj[prereq]:
        indegs[course] -= 1  # one more prereq satisfied
        if not indegs[course]:
            # all prereqs satisfied
            queue.append(course)
 
return taken == numCourses

Approach 2: DFS

adj = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
    adj[prereq].append(course)
 
visited = [False] * numCourses
in_stack = [False] * numCourses
 
def dfs(v):
    nonlocal visited, in_stack, adj
 
    if in_stack[v]:
        return True
    if visited[v]:
        return False
 
    visited[v] = True
    in_stack[v] = True
 
    if any(dfs(neighbor) )
    for neighbor in adj[v]:
        if dfs(neighbor):
            return True
 
    in_stack[v] = False
    return False
 
return not any(dfs(v) for v in range(numCourses))