algorithm - 蕴涵图分配

Question

蕴涵图是一个有向图，其中每个节点都被指定为真或假，并且任何边都u -> v暗示if u is true then v is true。

我知道一种简单的O(n^2)算法，可以在一般蕴涵图中找到分配以及O(n)某些特殊情况的算法（例如由2-SAT问题引起的蕴涵图）。

所以我想知道是否有O(n)算法找到任何暗示图的分配？

Answer 1

使用Tarjan 强连通分量方法可以找到满足蕴涵图的分配，因为该方法适用于所有蕴涵图，而不仅仅是通过转换 2-SAT 实例生成的蕴涵图。该方法由少量图形转换步骤组成，所有这些步骤都需要与输入大小成线性关系的时间。因此，整个算法需要 O(n) 运行时间。