2-SAT 问题

· · 个人记录

一、概念

2-SAT 问题可大致描述如下：

有 n 个变量，每个变量 a_i 只有两种可能的取值 a_{i, p}, a_{i, 1-p} (p \in \{1, 0\})。

再给定 m 个条件，每个条件都是对两个变量的取值限制，可转化为：若 a_i 赋值为 a_{i, p}，则变量 a_j 必须赋值为 a_{j, q}。

求 n 个变量的合法赋值。

二、算法

  1. 如何想到

想到使用 有向图连通性 来维护“选了……就必须选……”这种关系。

结合之前 并查集 中的 “扩展域并查集”，可以想出算法。

具体来说，a_{i, p} 向 a_{j, q} 连有向边，a_{j, 1-q} 向 a_{i, 1-q} 连有向边。这是因为原命题可推出 逆否命题。

  1. 比较二者

扩展域并查集 维护的关系是一种 双向 的：原命题、逆命题、否命题、逆否命题。这是它所连的两条双向边的本质。

而 2-SAT 问题 维护的关系则是 单向 的，不能推出逆命题、否命题，但可以推出 逆否命题。

  1. 判断无解

若 a_{i, 0} 与 a_{i, 1} 在同一个强连通分量内，问题无解。

  1. 求出特解

先将该图缩点，然后不断选择“零出度点”（逆拓扑序）。

选择零出度点没有后效性——或者说，让应该选择的点的“后继”都被选完。

三、应用

作者做过的都是板子（