Как найти действительный набор литералов из 2-SAT
это проблема 2-выполнимости. Я могу определить, удовлетворяются ли условия 2, используя алгоритм Косараю.
Например, для первого теста,
- +1 +3
- +2 -1
- +2 -3
- -1 -2
Я получил этот график импликации. Здесь я представил -1 до -3, используя узел 4-6.
Итак, 1 и 4, 2 и 5, 3 и 6 - пары, которые не принадлежат одному и тому же scc. Итак, вышеприведенные условия выполняются.
У меня вопрос, как найти правильный набор? Для этого тестового примера допустимый набор равен {2,3}. Любая помощь / предложение приветствуется.