我有一组学生(为概括起见，在标题中称为项目)。在这些学生中，有些人以粗鲁着称。我们被告知一组“我讨厌 j”形式的仇恨关系。 “我讨厌 j”不暗示“j 讨厌我”。我们应该将学生排成一排(最前面的排编号为 1)，如果“我讨厌 j”，那么我应该被排在严格编号小于j(换句话说:在 j 行前面的某行中)这样我就不会向 j 扔任何东西(不允许回头)。找到所需的最少行数(每行不需要有相同数量的学生)的有效算法是什么？
我们将做出以下假设:
1) 如果我们将其建模为有向图，则图中没有循环。最基本的循环是:如果“我讨厌 j”为真，“j 讨厌我”为假。因为否则，我认为订购将变得不可能。
2) 小组中的每个学生都至少被另一名学生讨厌或至少讨厌另一名学生。当然，也有一些学生既被一些人讨厌，又反过来讨厌其他学生。这意味着没有不构成图表一部分的离群学生。
更新: 我已经考虑过用 i --> j if 'i hates j 构造一个有向图并进行拓扑排序。但是，如果我必须将所有学生排成一行，一般拓扑排序会更适合。因为这里的行有变化，所以我试图弄清楚如何将变化考虑到拓扑排序中，以便它给我想要的东西。
当您回答时，请说明您的解决方案的复杂性。如果有人提供代码并且您不介意语言，那么我更喜欢 Java，但当然任何其他语言都一样好。
JFYI 这不适用于任何类型的家庭作业(顺便说一句，我不是学生 :))。
最佳答案
在我看来你需要调查 topological sorting .
关于在一组项目中建立排序的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/689535/