0207.Course Schedule

Link: 207. Course Schedule - Medium
Track: NeetCode150

Question

Restate the problem

• Given an integer number of courses and a list of prerequisite pairs
• Each pair a->b means course a must be taken before course b
• Return whether it is possible to finish all courses

Edge Case

• numCourses = 0 → return true
• Graph has a cycle → return False

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	BFS (Topological Sort)	$O(V+E)$	$O(V+E)$
Method 2	DFS (Detect Cycle)	$O(V+E)$	$O(V+E)$

Method 1 - BFS (Topological Sort)

Key idea: Use BFS topological sort: repeatedly take courses with indegree == 0, and if we can process all courses, then there is no cycle.

Approach

• Build a directed graph where an edge pre -> course
• An indegree array to record the number of prerequisites for each course
• Initialize a queue with all courses that have indegree 0
• While the queue is not empty:
  • Pop one course from the queue (this course is completed)
  • For each neighboring course:
    • Decrease its indegree
    • If indegree becomes 0, add it to the queue
• If all courses are processed, return true; otherwise, return false

Complexity

• Time Complexity: $O(V+E)$
• Space Complexity: $O(V+E)$
  • e.g., graph = {0:[1], 1:[]}, store edge

Code

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        degree = [0] * numCourses
        
        graph = defaultdict(list)
        for course, pre in prerequisites:
            degree[course] += 1
            graph[pre].append(course)
        
        queue = deque()
        taken = 0
 
        for idx in range(len(degree)):
            if degree[idx] == 0:
                queue.append(idx)
                taken += 1
 
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                degree[nei] -= 1
                if degree[nei] == 0:
                    queue.append(nei)
                    taken += 1
 
        return taken == numCourses

Method 2 - DFS (Detect Cycle)

Key idea:
Use DFS to follow each course’s prerequisite chain and detect whether it forms a cycle.
对每门课向前追踪它的precourse，判断依赖链中是否会形成环。

Approach

• Initialize preMap to store each course’s prerequisites, since DFS follows the dependency chain backward from a course to its prerequisite courses.
• Use DFS to trace each course backward through its prerequisite chain
• Use a visiting set to record courses in the current recursion path
• If a course appears again in visiting, a cycle exists
• After a course is fully checked and no cycle is found, set preMap[course] = [] to avoid repeated work

Complexity

• Time Complexity: $O(V+E)$
• Space Complexity: $O(V+E)$
  • e.g., graph = {0:[1], 1:[]}, store edge

Code

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:        
        preMap = defaultdict(list)
        for course, pre in prerequisites:
            preMap[course].append(pre)
        
        visiting = set()
        
        def dfs(course):
            if course in visiting:
                return False
            if preMap[course] == []:
                return True
            
            visiting.add(course)
            for pre in preMap[course]:
                if not dfs(pre):
                    return False
            visiting.remove(course)
            
            preMap[course] = []
            return True
 
        for course in range(numCourses):
            if not dfs(course):
                return False
 
        return True

---

Mistake

• BFS topological sort usually builds: pre -> course
• DFS cycle detection usually builds: course -> pre