题目描述：

你是一位系统管理员，手里有两门课程的选课清单，清单里是一个由若干对 [课程A, 课程B] 组成的数组，含义是选修课程A之前，必须先选修课程B。请你判断是否可能完成所有课程的选修。

示例 1:

输入: 2, [[1,0]] 输出: true 解释: 总共有两门课程，课程编号分别为0和1。课程0是课程1的前置课程，因此可以先选修课程0，再选修课程1。

示例 2:

输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有两门课程，课程编号分别为0和1。课程0是课程1的前置课程，同时课程1也是课程0的前置课程，这会导致循环依赖，因此无法完成所有课程的选修。

思路分析：

这道题实际上是一个经典的拓扑排序问题，常用于判断一个有向图中是否存在环。我们可以通过以下步骤来解决这个问题：

1. 构建邻接表和入度表：
   • 邻接表：用于存储每个课程的后续课程。
   • 入度表：用于存储每个课程的前置课程数量。
2. 初始化队列：
   • 将所有入度为0的课程（即没有前置课程的课程）加入队列。
3. 进行拓扑排序：
   • 从队列中逐个取出课程，并将其从邻接表中删除，同时将其后续课程的入度减1。
   • 如果某个后续课程的入度减为0，则将其加入队列。
   • 重复上述过程，直到队列为空。
4. 判断是否完成所有课程的选修：
   • 如果最终所有课程的入度都为0，则说明可以完成所有课程的选修，返回true。
   • 否则，说明存在循环依赖，返回false。

代码实现：

from collections import deque, defaultdict

adj_list = defaultdict(list)
in_degree = [0] * numCourses

for dest, src in prerequisites:
    adj_list[src].append(dest)
    in_degree[dest] += 1

# 初始化队列
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])

# 进行拓扑排序
visited_courses = 0
while queue:
    course = queue.popleft()
    visited_courses += 1
    for neighbor in adj_list[course]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

# 判断是否完成所有课程的选修
return visited_courses == numCourses

print(canFinish(2, [[1,0]])) # 输出: true print(canFinish(2, [[1,0],[0,1]])) # 输出: false

复杂度分析：

• 时间复杂度： O(V + E)，其中V是课程数量，E是课程依赖关系的数量。我们需要遍历所有课程和依赖关系来构建邻接表和入度表，并进行拓扑排序。
• 空间复杂度： O(V + E)，邻接表和入度表的总空间复杂度为O(V + E)。

通过上述分析和代码实现，我们可以有效地判断是否可能完成所有课程的选修。希望这个解答对你有所帮助！如果有任何进一步的问题，欢迎继续提问。