在O(n)中提出算法

Question

这是要解决的问题:

ñ矮人制作米关于谁比谁(例如:贾森<蒂姆·伯顿<杰森等)高的语句,但有些矮人会撒谎的顺序,给我们错误的语句,因此,它是我们的工作,以检查是否有可能相应地按照它们的大小来命令矮人.结果是"可能"或"不可能"以防矮人撒谎.

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

如何在O(n)运行时中管理它？我已经尝试过一些带有很多for循环和递归的东西,但是当处理这个问题的大尺寸情况时,这可能不合适或者花费太多时间.后来我被告知要用O(n)运行时找出算法.

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

Answer 1

您使用定向图是正确的,因为这是拓扑排序问题.关键是你可能会获得许多起始节点而不是一个起点.因此,即使你想要O(n + m)时间复杂,你也需要O(n + m)空间.

该链接提到了可以检测周期的Kahn算法.可以使用同一链路中提到的简单DFS遍历来执行周期检测.那也是一种O(n + m)算法.