前置
定义
有学长者云：
\(2-SAT\) 问题是通过建立图论模型，在 \(O(n+m)\) 的时间复杂度内判断是否有解，若有解可以构造出一组合法解。
思路
值得注意的是在不同的题目中二元 \(bool\) 运算可能有差异，但是建图的基本思路大致相同。
来观摩一组 OI-Wiki 的例子：
核心
Tarjan 缩点大法
主要还是考虑如何更合适地建图。
再来一组例子：
假设有 \(a_1\) 、 \(b_2\) 和 \(a_2\) 、 \(b_1\) 两对，已知 \(a_1\) 和 \(b_2\) 间有矛盾，于是为了方案自洽，由于两者中必须选一个，所以我们就要拉两条有向边 \((a_1,b_1)\) 和 \((b_2,a_2)\) 表示选了 \(a_1\) 则必须选 \(b_1\) ，选了 \(b_2\) 则必须选 \(a_2\) 才能够自洽。
然后通过这样建边再跑一遍 \(Tarjan\) 判断是否有一个集合中的两个元素在同一个强连通分量中，若有则不可能，否则输出方案。构造方案只需要把几个不矛盾的强连通分量拼起来就好了。
输出方案时可以通过变量在图中的拓扑序确定该变量的取值。如果变量 \(\lnot x\) 的拓扑序在 \(x\) 之后，那么取 \(x\) 值为真。应用到 \(Tarjan\) 算法的缩点，即 \(x\) 所在强连通分量编号在 \(\lnot x\) 之前时，取 \(x\) 为真。因为 \(Tarjan\) 算法求强连通分量时使用了栈，所以 \(Tarjan\) 求得的强连通分量编号相当于反拓扑序。
时间复杂度为 \(O(n+m)\) 。
暴力DFS
直接选取图上一个点，沿着一条路径搜下去，如果一个点被选择了，那么这条路径以后的点都将被选择。
如果出现一个集合中的两者都被选择了，那么此即为矛盾情况。
例题
思路
这是一道模板题。
显而易见每个变量 \(x_i\) 都可以被分开存储，即拆分成 \(i\) 和 \(i+n\) ，分别表示 \(x_i=1\) 和 \(x_i=0\) ，则这两个事件是互斥的。
对于限制 \(x_i\) 的每个命题 \(a\) 和 \(b\) ，一定有一个为真，则可以写成
那么由此可连边建图 \((\lnot a,b)\) ， \((\lnot b,a)\) 。
在该图中，若节点 \(i\) 与 \(i+n\) 在同一个强连通分量中，即允许互相到达，则它们分别代表的互斥事件会同时发生，说明存在矛盾，即不存在一组合法的方案。
否则则有解。
构造合法解：
对原图缩点得到一张 \(DAG\) 。
\(Tarjan\) 算法赋给强连通分量的编号顺序与拓扑序是相反的，上文已有说明。
CODE
/*
Name: P4782 【模板】2-SAT 问题
By Frather_
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
/*=========================================快读*/
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
/*=====================================定义变量*/
int n, m;
const int _ = 5000050;
struct edge
{
int to;
int nxt;
} e[_];
int cnt, head[_];
int dfn[_], low[_], num;
int bel[_], b_num;
stack<int> s;
/*===================================自定义函数*/
void add(int from, int to)
{
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
}
void Tarjan(int u_)
{
dfn[u_] = low[u_] = ++num;
s.push(u_);
for (int i = head[u_]; i; i = e[i].nxt)
{
int v_ = e[i].to;
if (!dfn[v_])
{
Tarjan(v_);
low[u_] = min(low[u_], low[v_]);
}
else if (!bel[v_])
low[u_] = min(low[u_], dfn[v_]);
}
if (dfn[u_] == low[u_])
{
b_num++;
while (true)
{
int t = s.top();
s.pop();
bel[t] = b_num;
if (t == u_)
break;
}
}
return;
}
/*=======================================主函数*/
int main()
{
n = read();
m = read();
for (int i = 1; i <= m; i++)
{
int x = read();
int a = read();
int y = read();
int b = read();
if (a && b)
{
add(x + n, y);
add(y + n, x);
}
if (!a && b)
{
add(x, y);
add(y + n, x + n);
}
if (!a && !b)
{
add(x, y + n);
add(y, x + n);
}
if (a && !b)
{
add(x + n, y + n);
add(y, x);
}
}
for (int i = 1; i <= n * 2; i++)
{
if (!dfn[i])
Tarjan(i);
if (i <= n && bel[i] == bel[i + n])
{
printf("IMPOSSIBLE\n");
return 0;
}
}
printf("POSSIBLE\n");
for (int i = 1; i <= n; i++)
printf("%d ", bel[i] < bel[i + n]);
return 0;
}
写在最后
最近被教练抓颓抓得好苦啊\kk
再次向已逝去的学长致敬（（（不是
鸣谢：
《算法竞赛进阶指南》
@LuckyBlock