拓扑排序算法实现与检测

"ACM拓扑排序算法实现与应用" 在计算机科学中，拓扑排序是一种对有向无环图（DAG，Directed Acyclic Graph）进行排序的方法，其结果是一个线性的序列，满足图中每条有向边u->v表示的顶点u都出现在顶点v之前。拓扑排序算法可以用于解决任务调度、依赖关系分析等问题。本问题探讨的是如何设计一个拓扑排序算法，不仅能处理DAG，还能检测是否存在环。 给定一个有向图，我们首先需要理解输入格式：第一行包含两个整数n和m，分别表示节点数和边数；接下来m行，每行两个整数，表示一条有向边。测试数据规模限定在n≤50，m<2500。 对于输出，如果图是DAG，输出一个拓扑排序序列，数字间用逗号分隔；若图包含环，则输出一个环，同样数字间用逗号分隔。 样例输入和输出展示了两种情况：一个无环的DAG和一个包含环的图。在有环的图中，输出的环展示了环中的节点顺序。 拓扑排序的基本思路通常采用深度优先搜索（DFS）或广度优先搜索（BFS）。这里给出的代码片段使用了DFS方法： 1. 定义一个`node`结构体，包含节点ID，前驱节点数组和后继节点数组。 2. `DFS`函数接收一个整数数组`s`，表示当前的排序序列，以及指向`node`结构体的指针`point`。该函数通过DFS遍历图，尝试将未访问的节点添加到排序序列中。 3. 在DFS过程中，如果发现环（即当前节点已存在于序列中），则输出"NO"和环中的节点序列，返回`true`。 4. 如果当前节点的所有后继节点都被访问过，说明无法继续拓扑排序，返回`false`。 5. 否则，选择一个未访问的后继节点，递归调用`DFS`。 在主函数`main`中，首先读取输入，然后创建一个二维数组`vArr`来存储边的信息。接着，使用DFS函数尝试进行拓扑排序，并根据返回值判断图是否为DAG。 注意，此代码示例没有处理所有边界条件，例如自环和重边。在实际应用中，应当确保处理这些特殊情况，以避免错误的结果。此外，为了提高效率和可读性，可以使用邻接表而非邻接矩阵来存储图信息，同时考虑使用BFS来实现拓扑排序，因为BFS通常能保证找到一个合法的排序，而DFS可能会因路径选择的不同导致不同的结果。 拓扑排序是图论中的一个重要概念，它在ACM竞赛和实际编程问题中都有广泛的应用。理解和掌握拓扑排序的原理及实现方法对于提升算法能力至关重要。