关于有依赖关系的算法怎么做--拓扑排序，课程表|| 力扣210题

今天看到一道题，就是课程表，主要问题是你如果想学习当前课程，可能需要先看前置课程有没有学完，这样才能学，有点像游戏里面的点技能点的意思。

这样有一个相关的依赖关系，此处在于。

参考liweiwei1419 大佬解析。

210. 课程表 II

难度中等700

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

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

这题居然是中等，卷的太厉害啦。

首先思考，课程表，先需求是拿出所有一开始就可以学习的表，那么就是判断每个技能依赖关系里面都没有前面一个的内容。，也即；
 

indegree = [i for i in range(numCoures)]
for second, first in prerequisites:
    indegree[second] += 1

这样再循环遍历整个indegree就能知道哪些是一开始就能学的，当然如果没有直接退出，也即这里面有循环根本学不了。

然后还得创建一个adj的表， 这里其实可以用defualDict来创建。

adj表在于将依赖关系写出来，这里用的是一个有set的列表。，

adj = [set() for _ in range(numCoures)]
for second, first in perrequesietst:
    adj[first].add(second)

这样整个传递关系就有了，然后思考一个技能树。肯定是先把第一层点完再继续下面的，所以用的层序遍历方法的队列。

q = deque()
for i in range(len(indegress)):
    if indegress[i] == 0:
        q.append(i)

然后对q进行循环判断就好，如果q内为空即已经无法继续下去，弹出。

while q:
    coures = q.ppoleft()
    res += [course]
    for i in adj[course]:
        indegress[i] -= 1
        if indegress[i] == 0:
            q += [indegress[i]]

结束的判断条件当然是当前res都用上所有课程即退出。