课程表

难度: Medium

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

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

例如，先修课程对 [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 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同

Submission

运行时间: 23 ms

内存: 17.1 MB

import collections
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        indegree = [0]*numCourses
        for x, y in prerequisites:
            graph[y].append(x)       #相当于建立了一个邻接表，存储了每个以y为先修课程的课程x
            indegree[x] += 1         #x之前有多少门先修课程，即x的入度
        queue = collections.deque([u for u in range(numCourses) if indegree[u] == 0])#哪些课入度为0
        while queue:
            node = queue.popleft()   #每修一门课
            numCourses -= 1          #待修课数-1
            for course in graph[node]:  #查看该课程对应的后继课程
                indegree[course] -= 1   #后继课程入度-1
                if indegree[course] == 0:  #没有先修课程了，加入queue
                    queue.append(course) 
        return numCourses == 0       #是否修完numCourses门课

Explain

这个题解使用了拓扑排序的思想。首先根据题目给定的先修课程关系构建一个有向图，每个课程代表图中的一个节点，如果课程A是课程B的先修课，则在图中添加一条从B指向A的有向边。同时统计每个课程的入度，即每个课程有多少门先修课程。然后将所有入度为0的课程加入队列，代表可以直接修读的课程。接下来进行BFS，每次从队列取出一门课程，将其指向的所有后继课程的入度减1，如果某个后继课程的入度变为0，则将其加入队列。最后判断是否学完了所有的课程，即`numCourses`是否减为0。

时间复杂度: O(V+E)

空间复杂度: O(V)

```python
import collections

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 构建有向图的邻接表表示
        graph = collections.defaultdict(list)
        # 统计每个课程的入度
        indegree = [0] * numCourses
        
        # 遍历先修课程关系，建图和统计入度
        for x, y in prerequisites:
            graph[y].append(x)  # 添加一条从y指向x的有向边
            indegree[x] += 1    # x的入度加1
        
        # 将所有入度为0的课程加入队列
        queue = collections.deque([u for u in range(numCourses) if indegree[u] == 0])
        
        # BFS拓扑排序
        while queue:
            node = queue.popleft()  # 取出一门可以修读的课程
            numCourses -= 1         # 待修课程数减1
            # 遍历该课程的所有后继课程
            for course in graph[node]:
                indegree[course] -= 1   # 后继课程的入度减1
                # 如果入度变为0，则加入队列
                if indegree[course] == 0:
                    queue.append(course)
        
        # 判断是否学完所有课程
        return numCourses == 0
```

Explore

在构建有向图时，选择从课程bi指向课程ai是为了反映课程ai必须在课程bi之前完成的关系。这样的表示方法使得入度（每个节点的入边数）直接对应于每个课程的先修课数量，方便在拓扑排序中直接使用入度为0的课程作为起始点。如果从ai指向bi，则需要额外的步骤或转换来识别哪些课程可以最先开始学习，增加了算法的复杂性。

在存在循环依赖的课程结构中，如[[1,0],[0,1]]，表示课程1依赖课程0，同时课程0又依赖课程1，形成了一个循环。在这种情况下，拓扑排序会发现没有任何课程的入度为0，因此初始队列为空。在BFS执行过程中，队列始终为空，没有课程的入度会被减至0。算法最终会返回false，表示无法完成所有课程的学习。这正是拓扑排序处理循环依赖的方式，即通过检测是否能遍历所有节点来判断是否存在循环依赖。

在这种场景下，使用BFS进行拓扑排序的优势在于其直观性和易于实现，特别是处理入度和队列的操作直接映射到课程的解锁过程。BFS能够逐层处理，每次都处理当前无依赖（或已解决依赖的）课程，这使得算法的执行逻辑清晰。而DFS虽然也可以用来进行拓扑排序，但其递归性质和后序遍历的特点使得实现相对复杂，尤其是在处理大规模数据时更容易遇到栈溢出的问题。此外，DFS在遇到循环依赖时需要额外的机制（如访问标记）来检测并处理循环，而BFS则通过简单的入度计数自然避免了这一问题。

如果在拓扑排序的过程中队列变为空，但仍有未处理的课程（即仍有课程的入度不为0），这通常意味着存在循环依赖，导致某些课程无法被解锁。在这种情况下，算法应该判断为无法完成所有课程的学习，返回false。这种情况下的空队列表明没有更多的课程可以无先修课程的限制下开始学习，进一步揭示了课程间的依赖关系存在闭环，阻止了某些课程的正常学习顺序。