Leetcode 207. Course Schedule

Let's understand what we're being asked to do. We have courses represented as nodes and prerequisite relationships as directed edges. For example, if course 1 requires course 0 as a prerequisite, we have an edge from 0 to 1.

Given numCourses = 2 and prerequisites = [[1,0]], this means course 1 depends on course 0. We can complete course 0 first, then course 1, so return true.

But consider numCourses = 2 and prerequisites = [[1,0],[0,1]]. Course 1 requires course 0, AND course 0 requires course 1. This creates a circular dependency - we can't complete either course! Return false.

Key constraint: We need to determine if a valid ordering exists where all prerequisites are satisfied before taking a course.

Edge cases to consider: What if there are no prerequisites at all? (all courses can be completed). What if a course has no prerequisites but other courses depend on it? What if there are multiple disconnected components in the graph?

Use depth-first search with cycle detection. For each course, recursively visit all its prerequisites, marking nodes as 'visiting' during traversal and 'visited' after completion. If we encounter a node marked 'visiting' during recursion, we've found a cycle. This approach explores all paths but may revisit nodes multiple times, making it less efficient than the optimal solution.

def can_finish(num_courses, prerequisites):
    """
    Determine if all courses can be completed using DFS cycle detection.
    Brute force approach: may revisit nodes multiple times during traversal.
    """
    # Build adjacency list: course -> list of prerequisites
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)
    
    # Track visiting state: 0=unvisited, 1=visiting, 2=visited
    state = [0] * num_courses
    
    def has_cycle(course):
        # If currently visiting this course, we found a cycle
        if state[course] == 1:
            return True
        
        # If already fully visited, no cycle from this node
        if state[course] == 2:
            return False
        
        # Mark as visiting
        state[course] = 1
        
        # Recursively check all prerequisites
        for prereq in graph[course]:
            if has_cycle(prereq):
                return True
        
        # Mark as visited
        state[course] = 2
        return False
    
    # Check each course for cycles
    for course in range(num_courses):
        if state[course] == 0:
            if has_cycle(course):
                return False
    
    return True

A course can only be completed if all its prerequisites are completed first. This means we need to process courses in an order where dependencies come before dependents.

The critical insight: if there's a cycle in the dependency graph (course A requires B, B requires C, C requires A), then no valid ordering exists because we'd need to complete A before starting A!

This transforms the problem from 'can we complete all courses?' to 'does the directed graph have a cycle?'

If the graph is acyclic (no cycles), we can find a topological ordering - a linear arrangement where all edges point forward. If there's a cycle, no such ordering exists.

Think about getting dressed in the morning. You must put on socks before shoes, underwear before pants. These are dependencies that form a directed graph.

If the rules were: 'put on shoes before socks' AND 'put on socks before shoes', you'd have a circular dependency - impossible to satisfy! But if the dependencies form a tree-like structure with no cycles, you can find a valid order to get dressed.

Use Kahn's algorithm for topological sorting with BFS. First, calculate the in-degree (number of prerequisites) for each course. Start with courses that have zero in-degree (no prerequisites) and add them to a queue. Process each course by removing it from the queue and decreasing the in-degree of all courses that depend on it. If a course's in-degree becomes zero, add it to the queue. If we process all courses, the graph is acyclic; otherwise, a cycle exists.

from collections import deque
def can_finish(num_courses, prerequisites):
    """
    Determine if all courses can be completed using Kahn's algorithm.
    Returns True if no cycle exists, False otherwise.
    """
    # Build adjacency list and calculate in-degrees
    graph = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Initialize queue with courses that have no prerequisites
    queue = deque()
    for course in range(num_courses):
        if in_degree[course] == 0:
            queue.append(course)
    
    # Process courses in topological order
    completed_count = 0
    
    while queue:
        current = queue.popleft()
        completed_count += 1
        
        # Reduce in-degree for dependent courses
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If all courses processed, no cycle exists
    return completed_count == num_courses

• Cycle detection via topological sort: When a problem asks if tasks with dependencies can be completed or if an ordering exists, recognize this as a directed acyclic graph (DAG) verification problem - use either Kahn's algorithm (BFS with in-degree tracking) or DFS with coloring to detect cycles, as cycles make topological ordering impossible.
• In-degree tracking pattern: Build an in-degree array counting incoming edges for each node, then use a queue initialized with all zero in-degree nodes - as you process nodes, decrement in-degrees of neighbors and add newly zero in-degree nodes to the queue; if you process all nodes, no cycle exists.
• Adjacency list construction: Convert the prerequisite pairs into an adjacency list representation (HashMap or array of lists) rather than using an adjacency matrix - this gives O(V + E) space instead of O(V²) and allows efficient neighbor iteration, critical when edges are sparse relative to possible connections.
• Three-state DFS coloring: For the DFS approach, use three states (unvisited, visiting, visited) to track node status - if you encounter a node in the 'visiting' state during DFS, you've found a back edge indicating a cycle; this is more reliable than just tracking visited nodes which can miss cycles in disconnected components.
• Complete traversal verification: A critical mistake is assuming no cycle exists just because DFS/BFS completes - you must verify that all N nodes were processed (count == numCourses in BFS, or all nodes marked visited in DFS), as disconnected components with cycles might be missed if you only start from one node.
• Dependency resolution systems: This pattern appears in build systems (Maven, Gradle), package managers (npm, pip), task schedulers, and database transaction ordering - any system where operations have prerequisites needs cycle detection to ensure valid execution order and prevent deadlocks.