AOV网与拓扑排序：解决幻灯片排序问题

"本次上机练习是关于拓扑排序与关键路径的问题，主要涉及如何将幻灯片的字母编号和数字编号对应，并通过拓扑排序的概念解决相关问题。" 拓扑排序是图论中的一个重要概念，尤其在处理有向无环图（Directed Acyclic Graph, DAG）时非常有用。在这个上机练习中，问题被设定为李教授需要整理他的幻灯片，这些幻灯片用数字1到n编号，并且已经用大写字母A到Z重新编号。你的任务是找到一种方式，使得数字编号和字母编号可以唯一对应，如果存在多种对应方式或者无法对应，则输出"None"。 首先，理解拓扑排序的基本原理。在一个AOV网（Activity On Vertex Network）中，每个节点代表一个活动，有向边表示活动之间的依赖关系，即一个活动必须在另一个活动完成后才能开始。一个有效的拓扑排序就是将这些活动按照没有前驱（入度为0）的活动开始，逐个加入序列，直到所有活动都被包含，且满足所有活动的前驱活动都在其前面。如果不能找到这样的序列，那么图中存在环，即有向图不是无环的，这种情况在实践中意味着活动的顺序无法确定或存在逻辑错误。 在这个问题中，幻灯片的字母编号和数字编号的关系可以被视为一种依赖关系。你可以将字母编号视为活动，数字编号视为它们的完成顺序。通过分析输入数据，你需要找出是否存在一种方式，使得每个数字编号的幻灯片（活动）可以按照其数字顺序被排列，同时与字母编号保持唯一对应。如果可能，输出字母和数字的对应关系；如果不可能，输出"None"。 具体实现拓扑排序算法时，通常采用以下步骤： 1. 初始化一个空的拓扑序列列表，以及一个记录每个节点入度的列表。 2. 遍历图的每个节点，找到入度为0的节点（没有前驱的活动），将其添加到拓扑序列列表中，并更新相关节点的入度。 3. 每次添加一个节点后，都要从图中移除这个节点及其作为起点的所有边，这样可以避免重复处理。 4. 如果所有节点都能被添加到拓扑序列中，那么说明图是无环的，拓扑排序成功；否则，如果仍有未添加到序列中的节点，说明图中存在环，拓扑排序失败。 在这个上机练习中，你需要实现上述算法来判断幻灯片的字母编号和数字编号是否能唯一对应。如果可以，输出每对字母和数字的对应关系；如果不能，输出"None"。在实现过程中，你可能会用到队列（如优先队列）来处理入度为0的节点，以及哈希表来快速查询节点的入度。注意，输出结果需要按照字母升序排列，且格式要符合题目要求。