207. Course Schedule

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/course-schedule
• topics: Graph, DFS

Description

There are a total of numCourses courses you have to take, 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.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Ideas

We need to sort topologically :

• DFS
• Kahn’s algorithm

Code

DFS

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

Kahn’s algorithm

class Solution:
    def canFinish(self, n: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        ans = 0
 
        for pair in prerequisites:
            course = pair[0]
            prerequisite = pair[1]
            adj[prerequisite].append(course)
            indegree[course] += 1
 
        queue = deque()
        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)
 
        while queue:
            current = queue.popleft()
            ans += 1
 
            for next_course in adj[current]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)
 
        return ans == n