207.课程表

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

一、dfs判断图是否有环

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

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

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