2-SAT 入坟

前置知识

• Tarjan
• 没了

问题与解法

问题

2-SAT 问题的模板题目是：

模板例题：对于 $n$ 个 bool 变量，变量值未知，给定 $m$ 个关系，每个关系形如：$x_i=c_1$ 或 $x_j=c_2$（$c_1,c_2\in\{0,1\}$）。求是否有给每个变量赋值的方案，若有解则输出一组解。时间复杂度要求线性。

这类问题就是 2-SAT 问题，更加进一步地，如果关系是：$x_i=c_1$ 或 $x_j=c_2$ 或 $x_k=c_3$。那就是 3-SAT 问题……现在已经被证明，3-SAT 或以上的 k-SAT 问题，是 NPC 的，1-SAT 问题应该不需要多说，所以重点就是 2-SAT 问题了。

解法

2-SAT 问题给出的是两个点之间的关系，对于 $a=1$ 或 $b=0$ 这样一个条件，我们可以推导出以下几个关系：

• 当 $a=0$ 时，$b$ 一定是 $0$。
• 当 $b=1$ 时，$a$ 一定是 $1$。

类似的，对于每一个种不同的关系，都可以推导出两个不同的式子：

于是我们根据“当什么什么时，得到什么什么”建立一个图。注意的是，这个关系是不能反过来的，比如表格第一个行结论 1：当 $b=0$ 时，一定有 $a=1$ 吗？并不是，此时 $a$ 可以是 $0$ 也可以是 $1$，不受约束。因此关系是定向的，不能反过来，翻译成建图就是，我们要建立有向图。

实际地说，对于每一个变量，我们要开两个点，为了方便我们用 $i$ 号点表示 $x_i$ 是 $0$，$i+n$（后文为了方便也记作 $i'$）号点表示 $x_i$ 是 $1$。

现在假设我们有以下几个关系：

• $a=1$ 或 $b=1$
• $b=1$ 或 $c=0$
• $a=0$ 或 $d=1$
• $c=0$ 或 $d=1$
• $a=0$ 或 $b=0$

拿第一个举例，$a=0$ 可以推出 $b=1$，所以 $a$ 向 $b'$ 连边；因为 $b=0$ 可以推出 $a=1$，所以 $b$ 向 $a'$ 连边。以上所有的关系的连边是：

a b'
b a'
b c
c' b'
a' d'
d a
c' d'
d c
a' b
b' a

得到的图：

现在发现，$a'$ 和 $b$ 在同一强连通分量内，$b'$ 和 $a$ 在同一强连通分量内，其他的点单独构成强连通分量。在同一强连通分量意味着这些变量有任意一个确定了取值，求可以推出全部强连通分量内的变量取值。假想一下如果 $a$ 和 $a'$ 在同一强连通分量意味着什么：$a=0$ 可以推出 $a=1$，而 $a=1$ 可以推出 $a=0$，此时就无解了。

也就是说：若对于一个变量 $x_i$，若 $x_i$ 和 $x_i'$ 在同一强连通分量内，一定无解，扫一遍即可。

现在这个图是一定有解了，如何找到一组解呢？我们假设得到了这样一个局部状态：

如果我们选择 $a=0$，那么 $a=0$ 可以推导出 $b=1$，进一步推导出 $a=1$，与 $a=0$ 出现矛盾。反之，如果选择 $a=1$，那么只能推出 $b=0$，但是 $a=1,b=0$ 恰好就是这个局部的一个可行解。从图论的角度看，对于同一个变量的两个点 $x_i$ 和 $x_i'，$我们选择了拓扑序较大的那个点。

进一步猜想一下，对于同一个变量的两个取值，选择缩点之后所在分量拓扑序较大的点是不是一定能构造出一组可行解呢？不妨来尝试证明一下：

先考虑一下这两个定理：

设 $u_0$ 表示节点 $u$，$u_1$ 表示节点 $u'$。

引理：若存在边 $(u_p,v_q)$，一定存在边 $(v_{1-q},u_{1-p})$。

证明：枚举法，见上文表格，对照即可。本引理在后文称作“引理一”。

引理：若存在一条单向路径 $u_p\rightarrow v_q$，则一定存在单向路径 $v_{1-q}\rightarrow u_{1-p}$。

证明：对路径上的每一条边都进行一次引理一得到。本引理在后文称作“引理二”。

假设 $\operatorname{f}(u_p)$ 表示 $u_p$ 所在的分量的拓扑序，并且有 $\operatorname{f}(u_p)<\operatorname{f}(u_{1-p}),\operatorname{f}(v_q)>\operatorname{f}(v_{1-q})$。若存在路径 $v_q\rightarrow u_p$，则说明取拓扑序大的这一做法不成立。

根据引理二，存在路径 $u_{1-p}\rightarrow v_{1-q}$，由前一个路径，$\operatorname{f}(v_q)<\operatorname{f}(u_p)$，由后一个路径，$\operatorname{f}(u_{1-p})<\operatorname{f}(v_{1-q})$

联立：

$\begin{cases} \operatorname{f}(u_p)<\operatorname{f}(u_{1-p}) \\ \operatorname{f}(v_q)<\operatorname{f}(u_p) \\ \operatorname{f}(u_{1-p})<\operatorname{f}(v_{1-q}) \end{cases}$

所以有：

$\operatorname{f}(v_q)<\operatorname{f}(u_p)<\operatorname{f}(u_{1-p})<\operatorname{f}(v_{1-q})$

这与 $\operatorname{f}(v_q)>\operatorname{f}(v_{1-q})$ 是矛盾的。也就是说取拓扑序大的这一做法是成立的。证毕。

那么现在的问题就是处理拓扑序了，显然可以直接缩点然后拓扑。

考虑到 Tarjan 标记强连通分量的时候，缩点的时候一定是先把靠近叶子节点的点缩掉了，而在搜索树上，拓扑序越大的点就是越靠近叶子节点的。因此 Tarjan 缩点的时候已经求出各分量的拓扑序了，但是是反序，因为先缩的点更靠近叶子，拓扑序也越大。

所以所在分量拓扑序更大，等价于 Tarjan 后所在强连通分量标号更小。

因此总的算法是：

1. 根据变量关系建图，注意图中有 $2n$ 个点，$2m$ 条有向边。
2. Tarjan 算法进行缩点。
3. 此时枚举每一个点，若 $x_i$ 和 $x_i'$ 在同一强连通分量，无解。否则有解。
4. 枚举每一个点，对于 $x_i$ 和 $x_i'$，取所在分量标号更小的那个点对应的取值，得到一组可行解。

时间复杂度 $\operatorname{O}(n)$ 级别。

代码

洛谷P4782模板

// Problem: P4782 【模板】2-SAT 问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4782
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int max_n=2000006;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
struct graph{
	int ct,hd[max_n],to[max_n*2],nx[max_n*2];
	graph(){ct=1;}

	inline void clear(){
		ct=1;
		memset(hd,0,sizeof(hd));
	}
	inline void add(int u,int v){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
	}
}e;

int n,m,tot,col[max_n];

stack<int> s;
bool in[max_n];
int cntdfn,dfn[max_n],low[max_n];

inline void Tarjan(int u,int fa){ // 常规的Tarjan
	s.push(u),in[u]=1;
	dfn[u]=low[u]=++cntdfn;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(!dfn[v]){
			Tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(in[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		++tot;
		int v=u;
		do{
			v=s.top();s.pop();
			in[v]=0,
			col[v]=tot;
		}while(v!=u);
	}
}

// i     : i=0
// opp(i): i=1

#define opp(x) (x+n)

signed main(){
	n=read(),m=read();
	for(register int i=1;i<=m;++i){
		int a=read(),x=read(),b=read(),y=read();
		if(x==y && !x){ // 0 0
			e.add(opp(a),b),
			e.add(opp(b),a);
		}
		else if(x==y){ // 1 1
			e.add(a,opp(b)),
			e.add(b,opp(a));
		}
		else if(!x){ // 0 1
			e.add(opp(a),opp(b)),
			e.add(b,a);
		}
		else{ // 1 0
			e.add(a,b),
			e.add(opp(b),opp(a));
		}
	}
	for(register int i=1;i<=n*2;++i) // Tarjan
		if(!dfn[i])
			Tarjan(i,i);

	for(register int i=1;i<=n;++i)
		if(col[i]==col[opp(i)]){ // 和 i' 在同一分量，无解
			puts("IMPOSSIBLE");
			return 0;
		}
	puts("POSSIBLE");
	for(register int i=1;i<=n;++i){
		if(col[i]<col[opp(i)]) // 因为是反序，取编号小的
			write(0);
		else
			write(1);
		putchar(' ');
	}
	return 0;
}

2-SAT活用

2-SAT 例题

先看一个变式，虽然题目中并没有经常出现，但是万一哪天有一个毒瘤题让你建模成这种形式呢：

对于 $m$ 组关系，有两种形式：第一种是 $x_i=c_1$ 或 $x_j=c_2$；第二种是：$x_i=c_1$ 且 $x_j=c_2$

看起来花里胡哨，实际上相当于直接送给你两个变量取值了，跑的时候直接从已知点往外推就行，对于已知结果的点也就不需要判拓扑序了。

洛谷上，带 2-SAT 标签的题目不算多，大多以紫题为主，简单举例。

NOI2017 游戏：每种场地有不同的赛车需求，有 ABC 三种赛车，有若干个不同场地选择赛车的需求，还需要满足：a 场地不能用 A，b 场地不能用 B，c 场地不能用 C，x 场地无限制。x 场地个数不超过 $8$。

对于 a,b,c 场地，可以转化为每个场地只适合两个赛车的情况，即对于 a 号场地，把 $i$ 和 $i'$ 当作“适合 B 赛车”和“适合 C 赛车”，以此类推。对于 x 类型的场地，因为个数很小，可以枚举每个场地不允许走 A 或者不允许走 B，转化成 2-SAT 问题。

HNOI2010 平面图判定：给定一个保证有哈密顿回路的图，求是否是平面图。

将哈密顿回路看作一个圆，其他边是圆上的弦，考虑是否要把弦翻到圆外。枚举两个在圆内有交点的弦，可以知道必须是一个在外一个在内的，具体见我的题解。

POI2001 和平组委员会：给定 $2n$ 个人以及之间的相互厌恶关系，每两个人属于一个党，每个党选一个人作为代表，且所有代表之间不能有相互厌恶关系。

可以将每个党派当作一个变量，$x_i=0$ 表示选择这个党第一个人，$x_i=1$ 表示选择这个党第二个人。考虑两个人厌恶的情况，实际上就相当于两个代表不能一起上台，换言之，上了其中一个人，就不能上另外一个。这样就也转化从 2-SAT 模板的推论式了。若 $a$ 不喜欢 $b$，则 $a\rightarrow b'$，$b\rightarrow a'$。

2-SAT与并查集

并查集同样也是处理两个点之间的关系的东西，2-SAT 也是处理两个点关系的东西，二者之间有什么区别？

我们来看一个这道题，简化题意如下：

有很多变量和各不相同的公式，一个公式描述两个变量的关系。若知道 A 和 B 的关系、B 和 C 的关系，就知道了 A 和 C 的关系；若知道 A 和 B 两个不同公式得到的关系，就解出了 A 和 B 的值；若知道 A 和 B 的关系、A 的值，就能得到 B 的值。现在不断加入新公式，每次加入后输出可以知道多少个变量的值。

我们抓住其中的特点：

• 关系是确定的。
• 关系具有传递性。
• 是否可以求值根据关系具有传递性。
• 不断加入新条件，每次加入后都要求解一次多少个值。
• 对哪些点可以求值不在乎，只统计数量。

即使抛弃其他特点，单独看第四点，总不能每次加一个条件，重新跑一遍 Tarjan 吧。

假设我们并不在每次加边后都求值，而是在所有的加边结束后询问一次，那么是不是可以用 2-SAT 的思路，因为 $a,b$ 关系知道了，相当于知道 $a$ 就知道 $b$，知道 $b$ 就知道 $a$？那不久相当于在一个图上面跑强连通分量了吗。

下面回到原来的题目，对于“传递性”这一特征，2-SAT 也可以实现，“统计数量”则等价于在 Tarjan 里求强连通分量中变量的数量……解释起来貌似一切成型。

相反一个 2-SAT 的题目可不可以用并查集做？正如前面所说，这个“若什么什么，则什么什么”的关系是不能反过来的。因此，显然，单纯的用并查集做是不合理的，不过 2-SAT 模板题的题解中有并查集+拓扑序的做法，有兴趣的可以自行去找。