2-Satisfiability問題中的實現問題

Question

我想爲100000個文字實現2-SAT問題。所以會有20萬個頂點。所以我被困在從每個頂點有一個所有可到達頂點的數組，空間複雜度爲O(200000^2)，這是不可行的所以請爲此建議一個解決方案。請介紹一下2-SAT問題的有效實施。

Answer 1

從wikipedia：

... 2，滿足性可在多項式時間內解決。當觀察到Aspvall, Plass & Tarjan (1979)時，當且僅當實例的每個變量屬於蘊涵圖的不同強連通分量而非同一變量的否定時，2-可滿足實例纔是可解的。由於通過基於深度優先搜索的算法可以在線性時間中找到強連通分量，所以相同的線性時間限制也適用於2-可滿足性。

我不會假裝理解大多數該段的，但它會出現有是可用於解決2-SAT問題的算法，它是該參考文件中描述（ A linear-time algorithm for testing the truth of certain quantified boolean formulas）。它顯然可以在網上購買，價格約爲20美元。我不知道這是否有幫助，但它是！

更新：同一個文件的免費PDF可以找到here。信用轉至liori查找。

Answer 2

這整個線程有點搞砸了。是的，人們可以在線性時間內解決2-sat問題，但不能解決這個問題。求解2-sat的時間與蘊含的數量成線性關係，對於200 000個變量可達到（200000 * 199999）/ 2，此外，如果使用此解決方案，則需要大約相同的內存量。還有另一種解決方案（不使用強連接的組件，速度較慢但不需要太多內存）。