Leetcode 210. Course Schedule II

Problem

Leetcode 210 - Corse Schedule II

Example:

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

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Input: numCourses = 1, prerequisites = []
Output: [0]

Approach

Similar to Leetcode 207, we can use DFS and find all the outputs. We can use cycle to track the courses that we’ve visited, and visited set to track all the courses that we’ve done.

Here is the Python code for the solution:

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        req = {i: [] for i in range(numCourses)}

        visited, cycle = set(), set()
        for course, pre in prerequisites:
            req[course].append(pre)
        
        res = []
        def dfs(c):
            if c in cycle:
                return False
            if c in visited:
                return True

            cycle.add(c)
            for p in req[c]:
                if dfs(p) == False:
                    return False
            cycle.remove(c)
            visited.add(c)    
            res.append(c)
            return True
            
        for c in range(numCourses):
            if dfs(c) == False:
                return []    
        return res 

Time Complexity and Space Complexity

Time Complexity: $O(V+E)$

Space Complexity: $O(V+E)$