Course Schedule

Problem

https://leetcode.com/problems/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] = [a:sub:`i`, b:sub:`i`] indicates that you must take course b:sub:`i` first if you want to take course a:sub:`i`.

  • 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.

Constraints:

  • 1 <= numCourses <= 2000

  • 0 <= prerequisites.length <= 5000

  • prerequisites[i].length == 2

  • 0 <= a:sub:`i`, b:sub:`i`< numCourses

  • All the pairs prerequisites[i] are unique.

Pattern

Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Approaches

Code

from collections import defaultdict, deque


def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    in_degrees = defaultdict(int)

    for [a, b] in prerequisites:
        graph[b].append(a)
        graph[a]
        in_degrees[a] += 1
        in_degrees[b]

    queue = deque()
    for node, in_degree in in_degrees.items():
        if in_degree == 0:
            queue.append(node)

    courses = set()
    while queue:
        node = queue.popleft()
        courses.add(node)

        for neighbor in graph[node]:
            in_degrees[neighbor] -= 1
            if in_degrees[neighbor] == 0:
                queue.append(neighbor)

    if len(courses) == len(graph):
        return True
    else:
        return False

Test

>>> from course_schedule__topological_sort import canFinish
>>> canFinish(2, [[1, 0]])
True
>>> canFinish(2, [[1, 0], [0, 1]])
False
course_schedule__topological_sort.canFinish(numCourses: int, prerequisites: list[list[int]]) → bool