2-SAT
SAT is short for the satisfiability problem. Its general form is the k-satisfiability problem, or k-SAT. For \(k>2\) the problem is NP-complete, so we study only the case \(k=2\).
Definition
Put simply, in 2-SAT we are given \(n\) Boolean equations, each involving two variables: for example, \(a \vee b\) says that at least one of the variables \(a\) and \(b\) must hold. The task is to decide whether a satisfying assignment exists. There may be several, of course; problems usually ask for just one. We write \(\neg a\) for the negation of \(a\).
Approach
Luogu P4782 [Template] 2-SAT
There are \(n\) Boolean variables \(x_1\sim x_n\) and \(m\) conditions to be satisfied, each of the form "\(x_i\) is true/false or \(x_j\) is true/false": for example, "\(x_1\) is true or \(x_3\) is false", or "\(x_7\) is false or \(x_2\) is false".
The goal of the 2-SAT problem is to assign a value to every variable so that all the conditions are satisfied.
We express this problem with Boolean equations. Let \(a\) stand for "\(x_a\) is true" (so \(\neg a\) stands for "\(x_a\) is false"). Suppose somebody's two requirements are \(a\) and \(b\), that is, \((a \vee b)\): at least one of the variables \(a\) and \(b\) must hold. We build a directed graph from these relations between the variables. Each of "\(a\) holds" and "\(a\) does not hold" becomes a vertex of the graph, and the edges \(\neg a\to b\) and \(\neg b\to a\) say that if \(a\) does not hold, then \(b\) must hold, and likewise that if \(b\) does not hold, then \(a\) must hold. Once the graph is built, the 2-SAT problem can be solved with an SCC condensation algorithm.
| Original formula | Graph construction |
|---|---|
| \(\neg a \vee b\) | \(a \to b\) and \(\neg b \to \neg a\) |
| \(a \vee b\) | \(\neg a \to b\) and \(\neg b \to a\) |
| \(\neg a\vee\neg b\) | \(a \to \neg b\) and \(b \to \neg a\) |
Many 2-SAT problems come down to finding relations of the form "if \(a\) does not hold, then \(b\) holds".
Solution
What does it mean for two vertices to lie in the same strongly connected component? By the logical meaning of the edges described above, the conditions represented by two such vertices are either both satisfied or both unsatisfied.
With the graph built, we find the SCCs with Tarjan's algorithm and check, for every Boolean variable \(a\), whether the vertex for "\(a\) holds" and the vertex for "\(a\) does not hold" lie in the same SCC (a condition cannot be both satisfied and unsatisfied, nor both unsatisfied and not unsatisfied). If they do for some variable, report that there is no solution; otherwise a solution exists.
When reconstructing a solution, the value of a variable can be read off from its position in the topological order of the graph: if \(x\) comes after \(\neg x\) in topological order, set \(x\) to true. In terms of the condensation computed by Tarjan's algorithm, set \(x\) to true when the index of the SCC containing \(x\) is smaller than that of the SCC containing \(\neg x\). The reason is that Tarjan's algorithm finds strongly connected components with a stack: a component that comes later in the topological order of the condensed graph is visited later, so it is popped off the stack and contracted earlier and receives a smaller index. The SCC indices produced by Tarjan's algorithm are thus in reverse topological order.
The algorithm traverses the whole graph once. In this graph \(n\) and \(m\) are of the same order of magnitude, and computing the answer takes \(O(n)\) time, so the algorithm runs in \(O(n)\) overall.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | |
Example problems
Example 1
HDU3062 Party
\(n\) married couples are invited to a party. Because of the venue, only one person from each couple can attend. Among the \(2n\) people, some pairs are in serious conflict (never the two members of a couple, of course), and two people in conflict will not both appear at the party. Is it possible for \(n\) people to attend at the same time?
Following the analysis above, if the husband of couple \(a_1\) and the wife of couple \(a_2\) do not get along, we add an edge from the husband of \(a_1\) to the husband of \(a_2\) and an edge from the wife of \(a_2\) to the wife of \(a_1\). It then remains to compute the condensation, coloring each vertex by its component, and check whether a solution exists.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | |
Example 2
2018-2019 ACM-ICPC Asia Seoul Regional K TV Show Game
There are \(k\) lamps, each either red or blue, but their colors are not known at the start. There are \(n\) people; each of them picks three lamps and guesses their colors. A person who guesses the colors of two or more lamps correctly wins a prize. Decide whether there is a coloring of the lamps for which everybody wins a prize, and if so, output one such coloring.
According to Yu Wu, Solving 2-SAT Problems by Symmetry (in Chinese), to output a satisfying assignment of a 2-SAT problem it is enough to select and delete vertices bottom-up on the DAG obtained from Tarjan's condensation.
In an implementation, you can build the transpose graph of the DAG and run a topological sort on it. Alternatively, use the property that after Tarjan's condensation, the smaller the index of the component a vertex belongs to, the closer the vertex is to the leaves, and select vertices in components with smaller indices first.
The code below implements the second method.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | |
Practice problems
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: chu-yuehan, Ir1d, AndrewWayne, frank-xjh, 24OI-bot, Anguei, sshwy, ouuan, Early0v0, Konano, Enter-tainer, Backl1ght, guodong2005, algosheep, peiyangjiang, kenlig, H-J-Granger, ksyx, akakw1, felixesintot, Tiphereth-A, c-forrest, HeRaNO, not-exist (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.