Skip to content

Problem

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.

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Example 1:

**Input:** numCourses = 2, prerequisites = [[1,0|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.

Solve

We have solve 802. Find Eventual Safe States, which do the same problem. The course that can finish need to be a safe node in graph (node that can’t start a cycle path).

  • We change the input Graph Edges table into better Graph Adj Node table representation.
  • Run the already solve find safe node and get all finish-able course.
  • We now check every course, if we found one isn’t a is safe node then return False, else return True

Here we get the best approach, which is a DFS solution to find safe node. 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for i in range(numCourses)]
        for u, v in prerequisites:
            graph[u].append(v)

        is_safe_node = [None] * len(graph)

        def DFS(current_node_id):
            if not is_safe_node[current_node_id] is None:
                return is_safe_node[current_node_id]

            is_safe_node[current_node_id] = False
            for adj_node_id in graph[current_node_id]:
                if DFS(adj_node_id) == False:
                    return False

            is_safe_node[current_node_id] = True
            return True

        for course_id in range(numCourses):
            if not DFS(course_id):
                return False
        return True

I also give Simulation approach a try, which give almost the same in result. 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for i in range(numCourses)]
        for u, v in prerequisites:
            graph[u].append(v)

        indegree = [0] * len(graph)
        is_safe_node = [False] * len(graph)

        ref_table = [set() for _ in graph]
        found_safe_node = []

        for node_id, adjNodes in enumerate(graph):
            if len(adjNodes) == 0:
                found_safe_node.append(node_id)
                is_safe_node[node_id] = True

            indegree[node_id] = len(adjNodes)

            for adjNode in adjNodes:
                ref_table[adjNode].add(node_id)

        while len(found_safe_node) > 0:
            node_id = found_safe_node.pop(0)

            for ref_node in ref_table[node_id]:
                if is_safe_node[ref_node]:
                    ref_table[ref_node] -= set([node_id])
                    continue

                indegree[ref_node] -= 1
                if indegree[ref_node] == 0:
                    found_safe_node.append(ref_node)
                    is_safe_node[ref_node] = True

        for node_id, is_safe in enumerate(is_safe_node):
            if not is_safe:
                return False
        return True

Final comparation

Argo Time Submitted Status Runtime Memory Language
DFS 07/13/2023 12:14 Accepted 108 ms 17.6 MB python3
Simulation 07/13/2023 12:03 Accepted 112 ms 19.1 MB python3
Last update : October 13, 2023
Created : August 16, 2023