B3644

MujicaSaki · 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 号节点已经没有辈分比他还大的了。按照上面的步骤我们就可以完成此道题目了。