你能从拓扑上对一个完整的无圈有向图进行排序吗？

Question

如果您有一个完整的有向无圈图(即每个顶点与任何其他顶点都有一个正在进行的或传出的边)，则可以使用O(V+E) = O(V^2)中的经典拓扑排序算法对其进行拓扑排序，因为E= O(V^2)。

但是，我们能不能通过一个典型的O(n log )算法对它进行排序呢？因为我们总是可以比较两个顶点，我有这样的印象。有反例吗？

而且，我想这只有在图完成的情况下才能工作。即使这个图几乎是完整的，那么你也可以有两个比较两个没有边的顶点。

Answer 1

是的，如果输入图是无圈的，那么它定义了一个严格的弱序，其中a< b当且仅当从a到b有一个弧线，而且快速排序会给出唯一的拓扑顺序。

但是，通常情况下，如果不探测所有的弧线方向，就无法测试锦标赛是否是无环的。