背景
在一些游戏中，有科技树之类的设定。譬如必须要先点“煤炭采集”的科技点，再点“煤化工”和“蒸汽机”的科技点，在“蒸汽机”的科技点上，再点“火车”的科技点。在“煤化工”和“蒸汽机”的基础上，才有“有机化工”。
其实与其说是“科技树”，不如说是“科技图”，因为有时候一个科技点需要多个前置科技点，这是符合“图”的拓扑关系，是一个有向无环图。
那我们一个按照什么顺序解锁这些科技点呢？这就需要“拓扑排序”（Topological order）。
算法
拓扑排序的算法同样分为广度优先搜索和深度优先搜索。
广度优先搜索
广度优先搜索比较直观，并且得到的结果就是拓扑排序的结果。
- 首先，找到入度为 0 的结点，先访问这个结点。（即找到没有前置条件的科技点，先解锁这个。）
- 去除掉这个结点，以及它相关的边。（点完这个科技点了，其余相关的入度 -1。）
如此循环往复。
深度优先搜索
深度优先搜索要求每个结点有三种状态，分别是「未访问」「访问中」和「已访问」。
每一轮搜索时，任意选取一个「未访问」的节点 u，从节点 u 开始深度优先搜索。将节点 u 的状态更新为「访问中」，对于每个与节点 u 相邻的节点 v，判断节点 v 的状态，执行如下操作：
如果节点 v 的状态是「未访问」，则继续搜索节点 vv；
如果节点 v 的状态是「访问中」，则找到有向图中的环，因此不存在拓扑排序；
如果节点 v 的状态是「已访问」，则节点 v 已经搜索完成并入栈，节点 u 尚未入栈，因此节点 u 的拓扑顺序一定在节点 v 的前面，不需要执行任何操作。
当节点 u 的所有相邻节点的状态都是「已访问」时，将节点 u 的状态更新为「已访问」，并将节点 u 入栈。
https://leetcode.cn/problems/Jf1JuT/solution/wai-xing-wen-zi-dian-by-leetcode-solutio-to66/
习题
207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
判断其能否上完所有课程。
这是典型的拓扑排序问题。
class Solution:
def canFinish(self, numCourses: int, prerequisites) -> bool:
# 构造邻接表table和每门课的入度
table = [[] for _ in range(numCourses)] # 邻接表
indegress = [0] * numCourses # 入度
for prere in prerequisites:
table[prere[0]].append(prere[1])
indegress[prere[1]] += 1
queue = deque()
ans = []
# 找到入度为 0 的结点
for i in range(numCourses):
if indegress[i] == 0:
queue.append(i)
# 开始 BFS
count_vis = 0
while queue:
cur = queue.popleft()
count_vis += 1
for next in table[cur]:
indegress[next] -= 1
# 新的入度为 0 的结点
if indegress[next] == 0:
queue.append(next)
return count_vis == numCourses
851. 喧闹和富有
还是拓扑排序，边是从更富有的人指向比它穷的人。
class Solution:
def loudAndRich(self, richer, quiet):
# 构建邻接表和入度表
length = len(quiet)
table = [[] for _ in range(length)]
indegree = [0] * length
for r in richer:
table[r[0]].append(r[1])
indegree[r[1]] += 1
# 找到入度为 0 的人
queue = deque()
for i in range(length):
if indegree[i] == 0:
queue.append(i)
# 开始 BFS
ans = list(range(length))
while queue:
cur = queue.popleft()
for next in table[cur]:
if quiet[ans[next]] > quiet[ans[cur]]:
ans[next] = ans[cur]
indegree[next] -= 1
if indegree[next] == 0:
queue.append(next)
return ans
