Course Schedule II

Intuition

Solution

class Solution:
    def _dfs(self, node):
        if self.orders[node] != -1:
            return True
        if node in self.visited:
            return False

        self.visited.add(node)

        for child in self.requisites[node]:
            if not self._dfs(child):
                return False

        self.orders[node] = self.index
        self.index += 1
        return True

    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        self.requisites = defaultdict(list)
        for i, j in prerequisites:
            self.requisites[i].append(j)
        self.orders = [-1] * numCourses

        self.index = 0
        for node in range(numCourses):
            self.visited = set()
            if not self._dfs(node):
                return []

        result = [-1] * numCourses
        for course_id, index in enumerate(self.orders):
            result[index] = course_id
        return result