Graph

from collections import defaultdict

# 定义图的邻接表数据结构
graph = defaultdict(list)

# 图的所有顶点
vertices = list(graph.keys())

# 某个顶点的邻居节点
neighbors = graph[vertex]

from collections import defaultdict, deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    """numCourses: 2
    """prerequisites: [[1,0],[0,1]]
    # 1.构建有向图和入度数组
    graph = dafaultdict(list)
    indegree = [0] * numCourses

    # 2.计算入度
    for dest, src in prerequisites:
        graph[src].append(dest)
        indegree[dest] += 1

    # 3.拓扑排序
    processed_courses = 0
    # 初始化队列，将所有入度为0的节点入队
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    while queue:
        # 依次处理队列中的节点，移除该节点，并将其指向的节点的入度减1。
        course = queue.popleft()
        processed_courses += 1
        # 更新该节点的邻居节点的入度数：该节点被移除，邻居节点的入度减1
        for neighbor in graph[course]:
            indegree[neighbor] -= 1
            # 邻居节点的入度减到0，则将其加入队列。
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # 4.如果处理的节点数等于课程总数，说明可以完成所有课程
    return processed_courses == numCourses