leetcode-207 Course Schedule

[207] Course Schedule

Key Concept: Cycle Detection in Directed Graph - If there's a cycle in the prerequisite graph, it's impossible to finish all courses. Use DFS with three states (unvisited, visiting, visited) to detect cycles.

Topological Sort: If no cycle exists, courses can be arranged in topological order.

# There are a total of numCourses courses labeled from 0 to numCourses - 1.
# You are given an array prerequisites where prerequisites[i] = [ai, bi]
# indicates that you must take course bi first if you want to take course ai.
# Return true if you can finish all courses. Otherwise, return false.
#
# Example 1:
# Input: numCourses = 2, prerequisites = [[1,0]]
# Output: true
# Explanation: Take course 0, then course 1.
#
# Example 2:
# Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
# Output: false
# Explanation: To take course 1 you should have finished course 0, and vice versa.
#
# Constraints:
# 1 <= numCourses <= 2000
# 0 <= prerequisites.length <= 5000
# prerequisites[i].length == 2
# 0 <= ai, bi < numCourses

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build adjacency list
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[course].append(prereq)

        # Three states: 0 = unvisited, 1 = visiting, 2 = visited
        state = [0] * numCourses

        def has_cycle(course):
            if state[course] == 1:
                # Found a back edge - cycle detected!
                return True
            if state[course] == 2:
                # Already processed this course
                return False

            # Mark as visiting
            state[course] = 1

            # 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(numCourses):
            if has_cycle(course):
                return False

        return True

    # Approach 2: BFS with Kahn's Algorithm (Topological Sort)
    def canFinish2(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from collections import deque

        # Build graph and in-degree array
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses

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

        # Start with courses that have no prerequisites
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        count = 0

        while queue:
            course = queue.popleft()
            count += 1

            # Remove this course and update in-degrees
            for next_course in graph[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    queue.append(next_course)

        # If we processed all courses, no cycle exists
        return count == numCourses

# DFS: Time O(V + E), Space O(V + E)
# BFS: Time O(V + E), Space O(V + E)
#
# Key Pattern: Three-state DFS for cycle detection
# 0 = unvisited, 1 = visiting (in current path), 2 = visited