2-SAT

有 \(n\) 个变量 \(a_i\in\{0,1\}\)，有 \(m\) 条限制形如：若 \(a_i=x\) 则 \(a_j=y\)。问是否有解，以及在有解的情况下构造一组解。这样的问题就叫 2-SAT。

我们用 \(2\) 个点分别表示每个变量为 \(0\) 或 \(1\) 的两种情况，一共 \(2n\) 个点。一条命题体现为图上的一条有向边。由于任意命题的逆否命题和原命题同真假，因此一条 \(x\to y\) 的边对应一条 \(\overline y\to \overline x\) 的边。

引理 原问题有解的充要条件是，对于任意 \(i\in [1,n]\)，\(x_i\) 与 \(\overline x_i\) 不在一个 SCC 内。

必要性显然，我们给出一个构造来说明充分性：

构造 通过 Tarjan 求得 SCC，取每对 \(x_i\) 和 \(\overline x_i\) 中 SCC 编号较小的那个值。

读者自证不难，大体思路就是，只考虑 \(x_i\) 和 \(\overline x_i\) 那么构造肯定没问题，然后再证 \(x_i\) 的选择不会和 \(y_i\) 冲突。