這題以前覺得特別難，其實是簡化版的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
