这题以前觉得特别难，其实是简化版的topological sort，也就是只需要判断有没有环(circular dependency)和省掉了sort部分。可以用269 alien dictionary同样的DFS思路加以简化而成。
这是最近写得比较满意的python解法。
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
edges = {c: set() for c in range(numCourses)}
for prereq in prerequisites:
edges[prereq[1]].add(prereq[0])
seen = {}
def dfs(start):
if start in seen:
return seen[start]
seen[start] = False
for nxt in edges[start]:
if not dfs(nxt):
return False
seen[start] = True
return True
if not all(dfs(start) for start in range(numCourses)):
return False
return True对比一下大概半年前写得当时比较满意版本，其实算法差不多。有如下小改进让code更短了：
1. seen用了Tree和False表示走通了的和当前正在走的路径，比原来的更省事。看来2种状态是判断环和避免重新走原来走过的路所必要的。
2. 节点全部写进edges里面，edges = {c: set() for c in range(numCourses)} ，不管有没有dependency，省了 if i not in deps: 判断
3. 需要order的话，dfs参数start, edges, seen order。不需要的话order的话就省掉order，只要start, edges, seen。用函数内定义函数可以少写很多用来传递状态的参数。
class Solution(object):
def __init__(self):
self.UNKNOWN = 0
self.VISITED = 1
self.CANTAKE = 2
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
deps = {}
for pre in prerequisites:
if pre[0] in deps:
deps[pre[0]].add(pre[1])
else:
deps[pre[0]] = {pre[1]}
status = [self.UNKNOWN] * numCourses
for i in range(numCourses):
if self.okToTake(i, status, deps) == False:
return False
return True
def okToTake(self, i, status, deps):
if status[i] == self.CANTAKE:
return True
elif status[i] == self.VISITED:
return False
status[i] = self.VISITED
if i not in deps:
status[i] = self.CANTAKE
return True
for dep in deps[i]:
if self.okToTake(dep, status, deps) == False:
return False
status[i] = self.CANTAKE
return True
