> 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/207.-ke-cheng-biao.md).

# 207.课程表

<https://leetcode-cn.com/problems/course-schedule/>

## 一、dfs判断图是否有环

先修课程对 `[0, 1]`，即图的有向边1->0，由此构建邻接表。由于不确定是否存在环，需要用一个visited数组存储**全局**已访问过的节点，防止重复访问

再用一个onPath数组参与dfs回溯，表示**当前**已访问的节点，若同一个节点被重复访问，说明存在环

```python
class Solution:
    def canFinish(self, numCourses: int, prerequisites) -> bool:
        # 构建邻接表
        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

        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   #退出回溯前恢复现场
            return
        # 以每个节点为起始尝试遍历
        for i in range(numCourses):
            travel(i)
        return not self.hasCycle
```