人际网络网络营销是什么_企业邮箱多少钱一年_企业培训视频_百度高级搜索功能

题目：207. 课程表

难度：中等

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

 

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

 

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

一、模式识别

1.图论

课程表是经典的图论中的拓扑排序问题

拓扑排序有两种实现方式：BFS（卡恩算法）和DFS

2.BFS（卡恩算法）思路

核心思路：从入度为0的节点开始，每遍历一个节点删除一个节点，并不断统计入度为0节点，如果统计结果小于总数，证明

算法步骤：

1.初始化：记录入度和节点间的关系

2.BFS找0入度节点，每找到一个，将其删除（将其指向的所有节点的入度减一），并计数

3.对比统计数与节点总数是否相等

3.DFS思路

核心思路：从任意节点开始，DFS搜索路径，如果在某节点处搜索返回了原位，则证明有环

算法步骤：

1.初始化：记录节点间关系，并用visited数组记录是否已访问

2.DFS（回溯法）从0号位开始搜索路径，直到最后一号位，如果发现有环，则返回False

二、代码实现

1.BFS（卡恩算法）

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:inDegree = [0] * numCourses toMap = collections.defaultdict(list)for ch in prerequisites:i, o = ch[0], ch[1]inDegree[i] += 1toMap[o].append(i)ans = 0que = collections.deque()for i in range(numCourses):if inDegree[i] == 0: que.append(i)while que:node = que.popleft()ans += 1for i in toMap[node]:inDegree[i] -= 1if inDegree[i] == 0: que.append(i)# print(ans, numCourses)return ans == numCourses

2.DFS

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:def dfs(q):nonlocal validvisited[q] = 1for v in toMap[q]:if visited[v] == 0: dfs(v)if not valid: returnelif visited[v] == 1: valid = Falsereturn visited[q] = 2# result.append(q)valid = True# result = []visited = [0] * numCoursestoMap = defaultdict(list)for ch in prerequisites: toMap[ch[1]].append(ch[0])i = 0while i < numCourses and valid:dfs(i)i += 1return valid