k-SAT

2-SAT

2-SAT is solvable in polynomial time using the implication graph: it is unsatisfiable iff some variable and its negation belong to the same strongly connected component (SCC).

Vertex for each variable and a negation of a variable

Edge (a,b) iff there exists a clause equivalent to (¬ab)

2-SAT example

2-SAT - Algorithms for Competitive Programming

The goal of this project is to translate the wonderful resource http://e-maxx.ru/algo which provides descriptions of many algorithms and data structures especially popular in field of competitive programming. Moreover we want to improve the collected knowledge by extending the articles and adding new articles to the collection.

https://cp-algorithms.com/graph/2SAT.html

k-SAT

2-SAT

2-SAT example

Recommendations