Course Schedule

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.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Solution

In here we can use the same concept as Topological Sort (Kahn's algorithm).

class App:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        prerequisiteToCourse = defaultdict(lambda: [])
        indegreeMap = defaultdict(lambda: 0)

        for course, dependency in prerequisites:
            prerequisiteToCourse[dependency].append(course)
            indegreeMap[course] += 1
        
        toStudy = [course for course in range(numCourses) if indegreeMap[course] == 0]
        studied = set()
        
        while toStudy:
            currentCourse = toStudy.pop()
            studied.add(currentCourse)
            
            for nextCourse in prerequisiteToCourse[currentCourse]:
                if nextCourse in studied: 
                    # Cycle depdendency
                    return False

                indegreeMap[nextCourse] -= 1

                if indegreeMap[nextCourse] == 0:
                    toStudy.append(nextCourse)

        return len(studied) == numCourses

• Time complexity: $O(|V| + |E|)$ — $|V|$ is the number of course and $|E|$ is the number of dependency
• Space complexity: $O(|V| + |E|)$ — $|V|$ is the number of course and $|E|$ is the number of depnedency
  Note:

In here, for the visited set we can either add it in the nextCourse for loop or in the main loop is fine, we don't have to follow BFS Visited location. So the above code is correct or this following one is also correct:

# ...
toStudy = [course for course in range(numCourses) if indegreeMap[course] == 0]
studied = set(toStudy) # NOTE HERE

while toStudy:
	currentCourse = toStudy.pop()
	
	for nextCourse in prerequisiteToCourse[currentCourse]:
		if nextCourse in studied: 
			# Cycle dependency
			return False

		indegreeMap[nextCourse] -= 1

		if indegreeMap[nextCourse] == 0:
			toStudy.append(nextCourse)
			studied.add(nextCourse) # NOTE HERE

return len(studied) == numCourses

The reason why Graph Traversal > Common mistakes we add the visited set there is because at some point in the future we might visit the one that we're meant to visit.

In this case it's a bit different, we're not keep adding the next course everytime, we only add if indegreeMap[nextCourse] == 0, and that's guarding the other course to add the nextCourse in the toStudy queue.

Therefore, if we put the visited when we take the course, that's fine as well because that will only happen once.