在 O(n) 中提出一个算法
Coming up with an algorithm in O(n)
这里是要解决的问题：
N 矮人对谁比谁高做出 m 陈述
（例如：Jason < Tim、Burton < Jason 等），但有些矮人可能会在顺序上撒谎并给我们错误的陈述，因此我们的工作是检查是否可以相应地按矮人的大小排序。结果是 "Possible" 或 "Impossible" 以防矮人撒谎。
到目前为止，我理解了想象一个矮人的有向图（class 代表矮人）的想法，它应该告诉我们矮人本人的名字和更高的矮人的名字比他。由于这应该是生成树，如果图形包含循环，结果应该是 "Impossible"。
如何在 O(n) 运行时中管理它？我已经尝试了一些带有大量 for 循环和递归的东西，但是在处理这个问题的大型案例时，这要么不合适，要么会花费太多时间。后来有人告诉我宁愿找出一个运行时间为 O(n) 的算法。
我想知道当我要在某个运行时解决一个问题时，我应该如何改变我的思维方式。
您使用有向图是正确的，因为这是一个 Topological Sort 问题。关键是您可能会得到多个起始节点，而不是一个单一的起始点。因此，即使你想要 O(n + m) 时间复杂度，你也需要 O(n + m) space.
link 提到了一种可以检测循环的 Kahn 算法。可以使用同一个 link 中提到的简单 DFS 遍历来执行循环检测。那也是一个O(n + m)算法。
你可以做一个DFS scan and check if a back edge exists (more details here)
这里是要解决的问题：
N 矮人对谁比谁高做出 m 陈述 （例如：Jason < Tim、Burton < Jason 等），但有些矮人可能会在顺序上撒谎并给我们错误的陈述，因此我们的工作是检查是否可以相应地按矮人的大小排序。结果是 "Possible" 或 "Impossible" 以防矮人撒谎。
到目前为止，我理解了想象一个矮人的有向图（class 代表矮人）的想法，它应该告诉我们矮人本人的名字和更高的矮人的名字比他。由于这应该是生成树，如果图形包含循环，结果应该是 "Impossible"。
如何在 O(n) 运行时中管理它？我已经尝试了一些带有大量 for 循环和递归的东西，但是在处理这个问题的大型案例时，这要么不合适，要么会花费太多时间。后来有人告诉我宁愿找出一个运行时间为 O(n) 的算法。
我想知道当我要在某个运行时解决一个问题时，我应该如何改变我的思维方式。
您使用有向图是正确的，因为这是一个 Topological Sort 问题。关键是您可能会得到多个起始节点，而不是一个单一的起始点。因此，即使你想要 O(n + m) 时间复杂度，你也需要 O(n + m) space.
link 提到了一种可以检测循环的 Kahn 算法。可以使用同一个 link 中提到的简单 DFS 遍历来执行循环检测。那也是一个O(n + m)算法。
你可以做一个DFS scan and check if a back edge exists (more details here)