Course Schedule

Signal

"Can all these dependent tasks be ordered/finished" on a directed graph is a cycle-detection question in disguise — it's possible iff the prerequisite graph has no cycle, since a cycle means a course indirectly requires itself.

Approach

Build an adjacency list from prerequisite pairs, then detect a cycle in the directed graph. Two clean ways: Kahn's algorithm (repeatedly remove nodes with in-degree 0; if you can remove all nodes, there's no cycle), or DFS with a 3-color scheme (white/unvisited, gray/currently-on-the-recursion-stack, black/fully-done — a cycle exists iff DFS reaches a gray node).

Skeleton

build adjacency list + in_degree count
queue = all nodes with in_degree 0
processed = 0
while queue:
    node = queue.pop()
    processed += 1
    for neighbor in adj[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0: queue.push(neighbor)
return processed == n

Solution

from collections import deque


def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    adj: list[list[int]] = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    queue = deque(c for c in range(num_courses) if in_degree[c] == 0)
    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return processed == num_courses

Complexity

O(V + E) time — building the adjacency list and in-degree counts is O(E), and each node/edge is processed once during the BFS. O(V + E) space.

Pitfalls

• Getting the edge direction backwards (adj[course].append(prereq) instead of adj[prereq].append(course)) silently detects cycles in the wrong graph.
• Assuming a visited set is enough for DFS cycle detection — you need the 3-state distinction (in-progress vs done), since a node reachable by two different paths isn't a cycle unless it's still on the current path.
• This only answers yes/no; if asked for the actual valid order, return the processed list itself (this is "Course Schedule II") instead of just its length.