# LeetCode 207. Course Schedule--有向图找环--面试算法题--DFS递归，拓扑排序迭代--Python

2020/01/29 共 3338 字，约 10 分钟

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

``````Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
``````

Example 2:

``````Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
``````

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

DFS-Python解法如下：

``````class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
s = {}
res = set()
flag = 0

def helper(begin=-1, find=set()):
nonlocal flag, res, s
for i in s[begin]:
if i not in res:
if i in find:
flag = 1
return
helper(i, find=find)

for i in range(0, numCourses):
s[i] = set()
for i in prerequisites:
for i in range(0, numCourses):
helper(begin=i, find={i})
if flag == 1:
return False
return True
``````

``````class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
graph = [[] for _ in range(numCourses)]
visited = [0 for _ in range(numCourses)]
# create graph
for pair in prerequisites:
x, y = pair
graph[x].append(y)
# visit each node
for i in range(numCourses):
if not self.dfs(graph, visited, i):
return False
return True

def dfs(self, graph, visited, i):
# if ith node is marked as being visited, then a cycle is found
if visited[i] == -1:
return False
# if it is done visted, then do not visit again
if visited[i] == 1:
return True
# mark as being visited
visited[i] = -1
# visit all the neighbours
for j in graph[i]:
if not self.dfs(graph, visited, j):
return False
# after visit all the neighbours, mark it as done visited
visited[i] = 1
return True
``````

``````class Solution:
class Course(object):
def __init__(self):
self.being_visit, self.visit_done = False, False
self.pre_course = []

def is_cyclic(self):
if self.visit_done is True:
return False
if self.being_visit is True:
return True
self.being_visit = True
for course in self.pre_course:
if course.is_cyclic():
return True
self.being_visit = False
self.visit_done = True
return False

def canFinish(self, num_courses, prerequisites) -> bool:
l = [self.Course() for _ in range(0, num_courses)]
for (course1, course2) in prerequisites:
l[course1].pre_course.append(l[course2])
for i in range(0, num_courses):
if l[i].is_cyclic():
return False
return True
``````

``````class Solution:
def canFinish(self, num_courses, prerequisites) -> bool:
vertices = num_courses
adj_list = [[] for _ in range(0, vertices)]
in_degree = [0 for _ in range(0, vertices)]
for (course1, course2) in prerequisites:
in_degree[course2] += 1
q = [i for i in range(0, vertices) if in_degree[i] == 0]
count = 0
while q:
front = q.pop(0)
in_degree[i] -= 1
if in_degree[i] < 0:
return False
elif in_degree[i] == 0:
q.append(i)
count += 1
if count == vertices:
return True
else:
return False
``````