问对列表进行排序，了解其中一些元素的比较结果？

EN

让我们想象一下，您要对对象集合进行排序，并从它们生成一个图，每个对象都有一个节点。然后，您将得到一组表示比较进行情况的对列表。你可以把这些看作是图中的边:如果你知道对象x比对象y要小，那么你可以从x到y画一个边。

假设比较的结果是一致的-也就是说，您没有任何循环-您应该有一个有向无圈图。

想一想，如果你对这个DAG进行拓扑排序，会发生什么。最后，您将得到一个与所有约束一致的值的可能排序。原因是，在拓扑排序中，如果有从y到x的任何传递的边序列，就不会将元素x放在元素y之前，如果有一个传递的比较序列表明y先于x，则从y到x有一个传递的边序列。

实际上，您可以提出一个更强的声明: DAG的所有拓扑顺序的集合正是满足所有约束的所有可能的有序的集合。我们已经论证了每个拓扑序都满足所有的约束，所以我们现在所要做的就是证明每一个满足所有约束的序列都是一个有效的拓扑序。这里的论点是，如果你遵守所有的约束条件，你就不会把序列中的任何元素放在它传递性比较较小的东西之前，所以你永远不会把序列中的任何元素放在有路径的东西前面。

这给了我们一个很好的方法来解决这个问题:用这种方式形成的图，看看它是否有一个拓扑序。如果是这样的话，那么这种排序就是唯一的排序顺序。如果没有，那么就有两个或更多的订单。

那怎么做才是最好的呢？进行拓扑排序的标准算法之一是用索引树对每个节点进行注释，然后反复取出索引零的节点并调整其后继节点的索引。DAG有一个拓扑序，如果在执行这个算法的过程中，每个阶段都有一个索引零的节点，因为在这种情况下拓扑排序是强制的。

通过正确的设置和数据结构，您可以实现这一点，以便在时间上运行O(n + m)，其中n是节点数，m是约束数。我将把这些细节留给读者，作为一个众所周知的练习。:-)

你的问题可以归结为著名的拓扑排序。

证明"C包含足够的信息来排序“就是证明拓扑排序的唯一性：

如果拓扑排序具有排序顺序中的所有连续顶点对都由边连接的性质，则这些边在DAG中形成有向哈密顿路径。如果存在哈密顿路径，则拓扑排序顺序是唯一的；没有其他顺序尊重路径的边。相反，如果拓扑排序不形成哈密顿路径，则DAG将有两个或多个有效的拓扑序，因为在这种情况下，总是可以通过交换两个不通过边连接的连续顶点来形成第二个有效序。因此，尽管更一般有向图的哈密顿路径问题具有NP-硬度，但仍有可能在线性时间检验是否存在唯一序，以及是否存在哈密顿路径(Vernet & Markenzon 1997)。