> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/201-400/210.-ke-cheng-biao-ii.md).

# 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实现拓扑

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

```python
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]
```