前置芝士
拓扑排序
拓扑排序是一种在有向无环图（DAG）中对节点进行排序的算法，其中每个节点表示一个任务或活动，并且边表示任务之间的依赖关系。
在拓扑排序中，排在前面的节点不依赖于排在后面的节点，因此可以按照一定的顺序依次执行这些任务或活动。
Kahn算法（卡恩）
时间复杂度：O(N+M)
[算法流程]
- 初始化一个队列（FIFO）和一个存储结果的列表。
- 统计每个节点的入度（即节点有多少个前驱节点），并将入度为0的节点加入队列。
- 当队列非空时，执行以下步骤：
a. 从队列中取出一个节点。
b. 将该节点添加到结果列表。
c. 遍历该节点的所有邻居节点：- 将邻居节点的入度减1。
- 若邻居节点的入度为0，将其加入队列。
- 遍历结束后，如果结果列表的长度等于图中节点的个数，则拓扑排序成功；否则，图中存在环，无法进行拓扑排序。
- 求字典序最小的拓扑序，将Kahn算法中的队列转为优先队列（小根堆）