课程表~~~

DFS深度优先 先用字典记录所有的信息 但是可以用第二种方法 直接使用列表记录即可~~

class Solution:
 def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool:
 ## 也就是不是一个环
 record {}
 sign {}
 for i in range(len(prerequisites)):
 if prerequisites[i][0] not in record:
 record[prerequisites[i][0]] {prerequisites[i][1]:1}
 else:
 record[prerequisites[i][0]][prerequisites[i][1]] 1
 def dfs(sub, res):
 if res in sub and sub[res] -1:
 return False
 if res in sub and sub[res] 1:
 return True
 sign[res] 1
 sub[res] -1
 if res in record:
 for i in record[res]:
 if not dfs(sub, i):
 return False
 sub[res] 1
 return True
 for i in range(len(prerequisites)):
 if i in sign:
 continue
 if prerequisites[i][1] not in record:
 continue
 else:
 if not dfs({}, prerequisites[i][1]):
 return False
 return True

class Solution:
 def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool:
 ############### 这道题的一个突破点是看到可以用列表解决问题 列表还是很好用的~
 adjacency []
 record {}
 for i in range(numCourses):
 adjacency.append([])
 for i in range(len(prerequisites)):
 adjacency[prerequisites[i][0]].append(prerequisites[i][1])
 def dfs(i, res): ### 可能不同的支路都经过了 回溯的思想DFS
 if i in res and res[i] -1:
 return False
 if i in res and res[i] 1:###### 重点 这里代表的是其他支路走过了 所以可以的~
 return True
 res[i] -1
 record[i] 1
 for m in adjacency[i]:
 if not dfs(m, res):
 return False
 res[i] 1
 return True
 for i in range(len(prerequisites)):
 if prerequisites[i][0] in record:
 continue
 if not dfs(prerequisites[i][0], {}):
 return False
 return True