Implication graph
Clause (a ∨ b) → two implications: ¬a → b, ¬b → a. Build directed graph on 2N literals.
Advertisement
SCC solves it
If x and ¬x in same SCC → unsatisfiable. Otherwise: topological order of SCCs gives assignment.
Advertisement
Assignment
For each variable x, assign true iff SCC(x) comes after SCC(¬x) in topological order.
Complexity
O(N + M) via Tarjan or Kosaraju.