2-SAT 可以用于解决 $n$ 个为 $0/1$ 的变量之间的关系问题。每个限制形如 $x_i=a$ 与 $x_j=b$ 二者中至少满足一个。

其实 2-SAT 是 k-SAT 问题的弱化，而 k-SAT 问题是 NP 完全的。

LaTeX: \neg 非 \iff 等价 \vee 逻辑或 \wedge 逻辑与

算法概述：

注：$a$ 与 $\neg a$ 代表事件与其对立事件，而 $x_i$ 与 $\neg x_i$ 代表 $x_i=1/0$。

对于一个限制如 $a\vee b\iff \neg a\to b\text{ add }\neg b\to a$

$a\to b$ 的一条边的含义：若 $a$ 这个事件成立，则 $b$ 将会发生。

• 判断是否有解：建图后进行 tarjan 缩点，若 $x_i$ 与 $\neg x_i$ 处在统一连通块中，那么无解。

• 输出不唯一方案：tarjan 缩点后强连通分量 id 其实就是拓扑序，若 $id_{x_i}<id_{\neg x_i}$ 那么 $x_i=0$，否则 $x_i=1$。

其余建图 trick:

1. $a=1\iff \neg a\to a$，这样 $\{a=0\}$ 拓扑序必在 $\{a=1\}$ 之前，故限制 $a=1$。

2. $a=0\iff a\to\neg a$，同理

注意事项：

1. 每个点两个状态，所以是 2N 个点。

2-SAT 问题模板

练习题目：

371. 牧师约翰最忙碌的一天

读完题目感觉太简单了，这不是直接 2-SAT 即可吗。

P3825 NOI2017 游戏【待完成*】

对于 $d=0$ 的情况，本质上就是一个 2-SAT 问题。照样对于每一次赛车建立两个点代表使用两种不同跑车，分情况建边：

1. 若限制第 $i$ 赛车使用 $x$ 的话第 $j$ 次必须使用 $y$。但第 $i$ 次并不能使用 $x$，不需要建边。
2. 若第 $j$ 次不能使用 $y$，按照上面对点限制的方法限制 $i$ 不能使用 $x$ 即可。
3. 若都可以，我们建边 $i\to j$，$j’\to i’$（若第 $j$ 场没有使用 $y$，则不能使用 $i$，也即逆否命题与原命题等价）

对于 $d>0$ 的情况，看上去是一个 3-SAT 问题，但是 $d$ 很小，朴素的思路是暴力 $3^d$ 枚举 $a,b,c$ 三种跑道再运行 2-SAT。但是超时了，但其实我们只需要枚举两种状态，覆盖 $3$ 种赛车的情况即可，因为 假如一个 $x$ 存在选 $c$ 的方案，那么排除 $a$ 和排除 $b$ 都是可以跑出来的。

复杂度 $O(2^d\times (n+m))$