2023级算法C4上机赛

2023级软院学生第四次上机赛习题讲解

H 2024-TOPO!

思路分析

其实拓扑排序是有两种比较经典的算法的，但是这道题很巧妙地（菜菜觉得）禁用了其中一种。

题目相比普通的拓扑排序存在一个额外的限制条件，P.S. 对于拓扑排序不唯一的情况，先输出序号大的点，再输出序号小的点。即输出字典序最大的拓扑排序。

可能一开始会想，DFS是否也可以达到这个目的，只需要将得到的图按照点的序列升序排列然后遍历后反转序列即可

但是这只能处理在同一条连通路径上的点的次序，也就是不能跨连通路径选择最优点，举个例子的话就是

比如下面的图（图后期发现有点问题，把3换成4，4换成2，2换成3）

如果按dfs首先遍历选择了顶点4，那么下一个必然只有2号顶点这一个选项，然而此时的更优解应改转而选择3和5的那条通路继续走，然后最后转回2，实现拓扑排序后字典序最大

所以这题适合用Kahn算法，利用其对于各顶点没有路径限制的特点，用优先队列/最大堆来维护序号最大的无入度顶点，实现拓扑排序并满足字典序最大