自动搬运

查看原文

来自洛谷，原作者为

	MujicaSaki .

搬运于2025-08-24 21:14:07，当前版本为作者最后更新于2022-08-21 13:15:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

拓扑排序的模板题。

拓扑排序是一个有向无环图的所有顶点的线性序列。

该序列需要满足每个顶点出现且只出现一次和如果有一条 $A$ 到 $B$ 的路径，在序列中 $A$ 出现在 $B$ 的前面。

这道题目显然全部满足以上条件。如果不懂可以看下面样例的有向无环图。

拓扑排序的步骤：

• 计算每个点的入度。

• 入度为 $0$ 就加入队列。

• 当队列不为空则循环：

  • 取出队首元素并输出。

  • 遍历队首元素的连边，对应节点的入度 $-1$。

  • 当对应的节点入度为 $0$ 就加入队列。

我们看样例的图，其中 $1$ 到 $5$ 的入度分别为 $2$，$0$，$2$，$1$ 和 $2$。我们就把 $2$ 号节点加入队列。队首现在不为空，所以我们取出 $2$ 号节点，并且输出出来。这时候因为他没有祖先所以一定是现在辈分最大的所以输出出来。删除所有对应节点的入度之后我们会发现 $4$ 号节点入度为 $0$。所以加入队列。然后取出队首 $4$ 号节点并且输出。很明显他的祖先 $2$ 号节点已经没了，所以 $4$ 号节点已经没有辈分比他还大的了。按照上面的步骤我们就可以完成此道题目了。