[leetcode刷题笔记]拓扑排序

拓扑排序的基本思路：
1.求个顶点入度，入度为0入栈；
2.栈不为空，出栈访问，并且该顶点的所有邻接点入度-1，若入度为0，入栈
3.存在尚未访问的顶点，则有环，拓扑排序不存在；若无环，则拓扑排序存在

下面使用拓扑排序解决两道问题。

课程表

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

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    
    # 拓扑排序
    indegrees = [0] * numCourses
    adjective = [[] for _ in range(numCourses)]

    # 1.计算入度
    for cur,pre in prerequisites:
        indegrees[cur] += 1
        adjective[pre].append(cur)
    
    # 2.入度为0入栈
    stack = []
    for i in range(numCourses):
        if indegrees[i] == 0:
            stack.append(i)
    
    # 3.栈不为空，出栈访问,并且该顶点的所有邻接点入度-1
    while stack:
        pre = stack.pop()
        numCourses -= 1
        for cur in adjective[pre]:
            indegrees[cur] -= 1
            if indegrees[cur] == 0:
                stack.append(cur)
    
    # 4.判断收否有点未访问
    return numCourses == 0

课程表 II

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    
    # 拓扑排序
    indegrees = [0] * numCourses
    adjective = [[] for _ in range(numCourses)]

    # 1.计算入度
    for cur,pre in prerequisites:
        indegrees[cur] += 1
        adjective[pre].append(cur)
    
    # 2.入度为0入栈
    stack = []
    for i in range(numCourses):
        if indegrees[i] == 0:
            stack.append(i)
    
    res = []

    # 3.栈不为空，出栈访问,并且该顶点的所有邻接点入度-1
    while stack:
        pre = stack.pop()
        res.append(pre)
        numCourses -= 1
        for cur in adjective[pre]:
            indegrees[cur] -= 1
            if indegrees[cur] == 0:
                stack.append(cur)
    
    # 4.若拓扑排序存在返回数组
    return res if numCourses == 0 else []

课程表 III 与 课程安排 IV 虽为图问题，但使用拓扑排序尚未解决。感兴趣的小伙伴可以研究一下。