拓扑排序对顶点号重新安排

拓扑排序是针对有向无环图（DAG）的一种排序算法，它将图中的顶点排成一个线性序列，使得对于任何一条有向边(u, v)，顶点u都排在顶点v之前。这个序列并不唯一，因为不同的拓扑排序可能代表了不同的任务执行顺序。拓扑排序的一个关键应用是在任务调度、课程安排等领域。

拓扑排序的过程如下：
1. 选择一个入度为0的顶点，并将其从图中删除（即将该顶点输出到结果序列中，并移除所有从该顶点出发的边）。
2. 更新图中剩余顶点的入度，因为所有指向这些顶点的边中有一条边已经被移除。
3. 重复步骤1和2，直到图中没有入度为0的顶点或者所有顶点都已经被输出。

如果在删除顶点的过程中，发现没有入度为0的顶点，且图中仍然存在顶点，这说明图中存在环，因此该图不是DAG，无法进行拓扑排序。

相关问题

拓扑排序 ACWing

拓扑排序是一种对有向图进行排序的算法，它可以得到一个满足拓扑序列要求的图中点的排列顺序。给定一个有向图，拓扑排序要求每个顶点的入度都为0，并按照一定的顺序进行排序。如果一个图存在拓扑排序，则输出任意一个拓扑序列；如果不存在拓扑排序，则输出-1。

拓扑排序的实现方法有多种，其中一种常用的方法是使用深度优先搜索（DFS）完成。具体步骤如下：
1. 首先，遍历图的所有顶点，并记录每个顶点的入度。
2. 然后，从入度为0的顶点开始深度优先搜索，遍历该顶点的邻接顶点。
3. 在遍历邻接顶点的过程中，将遍历到的顶点的入度减1，并将入度减到0的顶点加入一个队列中。
4. 重复步骤2和步骤3，直到队列为空。
5. 最后，如果遍历过的顶点数量等于图中的顶点数量，则说明图存在拓扑排序，输出该排序；否则，输出-1。

拓扑排序可以应用于许多问题，如任务调度、课程安排等。它可以帮助我们确定一些具有依赖关系的事物的执行顺序。

ACWing是一个在线算法竞赛平台，提供各种算法题目和实时竞赛。在ACWing中，拓扑排序是一个常见的算法题目之一，用于测试算法竞赛选手对拓扑排序算法的理解和应用能力。

拓扑排序的逆序是逆拓扑排序吗

是的，拓扑排序的逆序就是逆拓扑排序。拓扑排序是一种对有向无环图进行排序的算法，它可以将有向无环图中的所有顶点排成一个线性序列，使得图中任意一条有向边的起点都排在终点的前面。而逆拓扑排序则是将拓扑排序的结果反过来，即将有向无环图中的所有顶点排成一个线性序列，使得图中任意一条有向边的起点都排在终点的后面。

在逆拓扑排序中，我们需要按照以下步骤进行排序：
1. 从有向无环图中选择一个没有前驱（入度为0）的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复1和2直到当前的有向无环图为空。

逆拓扑排序可以用于解决一些问题，例如任务调度问题、课程安排问题等。