2-SAT

什么是 $2-SAT$ 问题

给出 $n$ 个变量 $x_i$，每一个变量只能取 $1/0$ ，给出 $m$ 个条件，如 $x_i = 0/1 或 x_j = 0/1$， $2-SAT$ 就是求满足这 $m$ 个条件的一组解。

---

逻辑关系

根据逻辑关系，我们就可以把每一组条件进行转化，设每一组条件中的第一个是 $a$ ，另一个是 $b$ ，那么 $a$ 不成立 $b$ 一定成立，并且$b$ 不成立 $a$ 一定成立 。

---

拆点建图

我们把每一个变量看作一个点，把 $n$ 个点拆成 $2n$ 个点， 把 $x_i$ 拆成 $x_i 和 x_{i+n}$ 。
建图连有向边，例如对于条件 $x_i = a 或 x_j = b$ ，

$x_i != a 且 x_j = b$ 可以表示为从 $i + !a * n$ 到 $j + !b * n$ 连接一条有向边 。 ($!$表示取反)
$x_j != b 且 x_i = a$ 可以表示为从 $j + !b * n$ 到 $i + !a * n$ 连接一条有向边 。

---

Tarjan 缩点

1. 如果 $i$ 和 $i + n$ 在一个 $SCC$ 内， 说明无解，因为不能同时取 1 和 0 ；
2. 否则一定存在可行解。

---

构造可行解

如果有 $i -> ... -> i + n$ ，哪那么就选择 $i + n$ , $x_i= 1$ ;
如果有 $i + n -> ... -> i$ ，哪那么就选择 $i$ , $x_i= 0$ ;
蕴含关系具有传递性，选择后者，冲突性更小。

Tarjan 缩点后我们得到的是拓扑排序
因为先访问的节点后出栈，后出栈的节点SCC编号就大

所以如果 $SCC[i] > SCC[i+n]$, $x_i = 1$ ;
所以如果 $SCC[i] < SCC[i+n]$, $x_i = 0$ ;