[LeetCode Python3] 207. Course Schedule+ DFS

207. Course Schedule

该题本质是判断图中是否存在环，这里采用深度优先搜索求解

Solution:

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        def dfs(i):
            visited[i] = 1
            if i in graph:
                for tmp in graph[i]:
                    if visited[tmp] == 1: # 若遇到正在访问的节点，说明存在环
                        return False
                    elif not dfs(tmp):
                        return False
            visited[i] = 2
            return True
		# 根据条件建图
        graph = {}
        for i, j in prerequisites:
            if j in graph:
                graph[j].add(i)
            else:
                graph[j] = set([i])
        visited = [0]*numCourses    #0表示未访问，1表示正在访问，2表示访问过
        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i):
                    return False
        return True