210.课程表 II

https://leetcode-cn.com/problems/course-schedule-ii/

一、拓扑排序

https://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F

维护一个入度为0的队列，每次优先访问队列节点，并将相邻节点符合入度为0的入队，直到对空，若最后队列不能清空说明有环，否则访问的顺序就是拓扑排序

二、dfs实现拓扑

图后续遍历得到访问序列，再将序列逆序得到拓扑排序（如果存在的话）

class Solution:
    def findOrder(self, numCourses: int, prerequisites) :
        # 构建邻接表
        graph = {}
        for i in range(numCourses):
            graph[i] = list()
        for edge in prerequisites:
            f = edge[1]
            t = edge[0]
            graph[f].append(t)  # 写入邻接表

        visited = [False] * numCourses  # 记录访问过的节点
        onPath = [False] * numCourses

        postOrder = []
        self.hasCycle = False

        def travel(s):
            if onPath[s]:
                self.hasCycle = True
            if visited[s]:  # 访问过则停止
                return
            visited[s] = True  # 标记已访问
            onPath[s] = True  # 尝试访问该节点
            # 访问所有相邻节点
            for neigh in graph[s]:  
                travel(neigh)
            #后序遍历
            onPath[s] = False  # 退出回溯前恢复现场
            postOrder.append(s) #记录后序序列
            return

        # 以每个节点为起始尝试遍历
        for i in range(numCourses):
            travel(i)
        # 若无环则返回后序的逆序
        return [] if self.hasCycle else postOrder[::-1]