Назначение графа импликации

Question

Граф импликации - это ориентированный граф, в котором каждому узлу присваивается значение true или false, а любое ребро u -> v подразумевает, что if u is true then v is true,

Я знаю прямолинейно O(n^2) алгоритм, чтобы найти назначение в графе общего импликации и O(n) алгоритмы для некоторых особых случаев (например, граф импликации, возникающий из задачи 2-SAT).

Так что мне было интересно, если есть O(n) алгоритм найти назначение любого имплицитного графа?

Answer 1

Удовлетворительные назначения для графов импликации можно найти, используя метод сильно связанных компонентов Тарьяна, поскольку этот метод применим ко всем графам импликации, а не только к тем, которые получены путем преобразования экземпляров 2-SAT. Этот метод состоит из небольшого количества шагов преобразования графа, все из которых требуют времени, линейного к размеру входных данных. Таким образом, алгоритм в целом требует O(n) времени выполнения.