19.拓扑排序

拓扑排序

直接按照模板写，运用队列依次遍历节点。

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # 连通矩阵，f[i][j]==True表示i是j的先决条件。
        n=numCourses
        f=[[False]*n for _ in range(n)]
        # 存储节点后续节点
        g=[[]for _ in range(n)]
        # 节点的入度大小
        indeg=[0]*n
        # 初始化节点后续节点，节点的入度
        for a,b in prerequisites:
            g[a].append(b)
            indeg[b]+=1
        # 将入度为0的节点加入队列
        q=deque([i for i,x in enumerate(indeg) if x==0])
        # 当列表不空
        while q:
            # 取出一个节点
            i=q.popleft()
            # 依次遍历后继节点
            for j in g[i]:
                # 存在[i,j],则将f[i][j]设为True
                f[i][j]=True
                # 依次遍历所有节点，若存在f[h][i]为True,则将f[h][j]也设为True
                for h in range(n):
                    if f[h][i]:
                        f[h][j]=True
                # i到j处理完毕，将j的入度减1
                indeg[j]-=1
                # 若节点j入度为0，则加入队列
                if indeg[j]==0:
                    q.append(j)
        # 依次返回查询结果
        return [f[a][b] for a,b in queries]