2-SAT 笔记

本文于 2026-05-12 重写。

一、定义

$\vee$ 是或，$\wedge$ 是与。

给定长度为 $m$ 的序列 $p,q$，求一组合法的 $n$ 个 $0/1$ 变量 $x_{1\dots n}$，满足

$$\underset{i=1}{\overset{m}{\bigwedge }}(x_{p_i}\vee x_{q_i})=1$$

这个问题可以用 2-SAT 解决。

二、解决方法

我们把一个点 $x$ 拆成两个状态：$x_0$ 表示 $x=0$，$x_1$ 表示 $x=1$。在题目给出的限制中，显然这些状态是可以互相推理的。

1. $x\vee y=1$

$x_0\Rightarrow y_1$，$y_0\Rightarrow x_1$。

2. $\mathrm{\neg }x\vee y=1$

$x_1\Rightarrow y_1$，$y_0\Rightarrow x_0$。

3. $x\vee \mathrm{\neg }y=1$

$x_0\Rightarrow y_0$，$y_1\Rightarrow x_1$。

4. $\mathrm{\neg }x\vee \mathrm{\neg }y=1$

$x_1\Rightarrow y_0$，$y_1\Rightarrow x_0$。

如果用 $a$ 表示 $x=a$ 时原式一定为 $1$，$b$ 表示 $y=b$ 时原式一定为 $1$，那么观察可以得到：

$x_{a\oplus 1}\Rightarrow y_{b\wedge 1}$，$y_{b\oplus 1}\Rightarrow x_{a\wedge 1}$。

我们根据推理情况建有向图，跑强连通分量，如果存在 $x_0$ 和 $x_1$ 在同一强连通分量内，则说明无解。

当 $x_1$ 所在的强连通分量的拓扑序在 $x_0$ 所在的强连通分量的拓扑序之后取 $x=1$，Kosaraju 算法按拓扑序排好的，Tarjan 算法则是反着的拓扑序，要将 $sc{c}_{x_1}>sc{c}_{x_0}$ 改为 $sc{c}_{x_1}<sc{c}_{x_0}$。

证明如下：

考虑对于 $x\vee y=1$ 的建边操作，本质为 $\mathrm{\neg }x\to y$、$\mathrm{\neg }y\to x$。

如果取点 $x=1$ 和 $\mathrm{\neg }x=0$ 不可行，说明这样取或导致某个 $y$ 同时必须取 $y=0$ 和 $y=1$，即存在路径 $x\to y$ 和 $x\to \mathrm{\neg }y$。

又由建边的对称关系，存在路径 $\mathrm{\neg }y\to \mathrm{\neg }x$ 和 $y\to \mathrm{\neg }x$，整理可得存在路径 $x\to \mathrm{\neg }x$，即 $x_0$ 的强连通分量拓扑序比 $x_1$ 大。

cin >> n >> m;
for (int i = 1, x, a, y, b; i <= m; i++) {
    cin >> x >> a >> y >> b;
    add(x + n * (a & 1), y + n * (b ^ 1));
    add(y + n * (b & 1), x + n * (a ^ 1));
}
kosaraju();
for (int i = 1; i <= n; i++)
    if (scc[i] == scc[i + n]) {
        cout << "IMPOSSIBLE";
        return 0;
    }
cout << "POSSIBLE\n";
for (int i = 1; i <= n; i++)
    cout << (scc[i] > scc[i + n]) << " ";

三、建图优化

如果有这么一张 $n^2$ 的图：

举 $2$ 号点为例，发现它要这样连边：

所以弄两班公交车，一班向右走，一班向左走：

因为 $2$ 号点要去 $5$ 号点及其左边的点，所以他在 $13$ 号点上向左走的公交车；$7$ 号点应该要被 $2$ 号点及其左边的点去，$8$ 号点应该被 $3$ 号点及其左边的点去，所以将 $2$，$3$ 号点对应的公交站 $10$，$11$ 号点和 $7$，$8$ 号点连边。

剩下的点同理：

我们成功把边数优化到 $O(n)$ 级别的（由于常数是 $6$，上图 $n=4$，所以看起来像是还更多边了，实则当 $n$ 有一定大小时并不是）。