algorithm - 在 O(n) 中提出一个算法

Question

这里是要解决的问题:

N 个矮人做出了关于谁比谁高的 m 个陈述(例如:Jason < Tim、Burton < Jason 等)，但有些矮人可能会在顺序上撒谎并给我们错误的陈述，因此我们的工作是检查是否可以相应地按矮人的大小排序。如果侏儒说谎，结果要么是“可能”，要么是“不可能”。

到目前为止，我理解想象一个矮人的有向图(有一个矮人类)的想法，它应该告诉我们矮人本人的名字和比他高的矮人的名字。由于这应该是生成树，因此如果图形包含循环，则结果应为“不可能”。

我如何在 O(n) 运行时中管理它？我已经尝试了一些带有大量 for 循环和递归的东西，但是在处理这个问题的大型案例时，这要么不合适，要么会花费太多时间。后来有人告诉我宁愿找出一个运行时间为 O(n) 的算法。

我想知道当我应该在某个运行时解决一个问题时，我应该如何改变我的思维方式。

Answer 1

您使用有向图是正确的，因为这是一个 Topological Sort问题。关键是您可能会得到多个起始节点，而不是一个单一的起始点。因此，即使您想要 O(n + m) 时间复杂度，您也需要 O(n + m) 空间。

该链接提到了可以检测循环的 Kahn 算法。可以使用同一链接中提到的简单 DFS 遍历来执行循环检测。这也是一个O(n + m) 算法。