Course Schedule 2

题目描述

解题方法

这一题的edge方向是和别的graph里反过来的，所以最后的stack不应该reverse.

Solution

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        edge_map = {}
        for pre in prerequisites:
            if pre[0] in edge_map:
                edge_map[pre[0]].append(pre[1])
            else:
                edge_map[pre[0]] = [pre[1]]
        visited = [0 for i in range(numCourses)]
        stack = []

        def dfs(course):
            if visited[course] == 1:
                return False
            if visited[course] == 2: # can return, cause all its dependency should be done
                return True
            visited[course] = 1
            if course in edge_map:
                for depend in edge_map[course]:
                    if not dfs(depend):
                        return False
            visited[course] = 2
            stack.append(course)
            return True

        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i):
                    return []

        return stack

Reference

• course schedule