一、问题描述
题目解析
本题是一个典型的拓扑排序问题。拓扑排序用于解决有向无环图(DAG)中的节点排序问题,使得对于图中的每一条有向边 (u, v),u 在排序中总是位于 v 的前面。在本题中,任务之间的依赖关系可以看作是有向图中的边,而任务的执行顺序就是拓扑排序的结果。
拓扑排序的基本思路
-
构建图:首先,我们需要根据输入的依赖关系构建一个有向图。图中的节点代表任务,边代表任务之间的依赖关系。例如,
A->B
表示任务 A 依赖任务 B,因此在图中有一条从 B 指向 A 的边。 -
计算入度:对于图中的每一个节点,计算它的入度(即有多少条边指向它)。入度为 0 的节点表示没有依赖的任务,可以立即执行。
-
拓扑排序:从入度为 0 的节点开始,依次将这些节点加入结果序列中,并移除它们以及它们指向