什么是2-SAT
2-sat问题是一个逻辑互斥问题，与我们小时候做过的一道数学题一样。
A,B,C三个人中有两个女生，其中如果A为女生，B一定不是女生，而且A与C性别相同，求A，B，C的性别。
这是一道非常简单的题目，我们可以简单分析一下。
我们用(f[i]=0)表示(i)为女生，(f[i]=1)表示(i)为男生，那么“如果A为女生，B一定不是女生”这句话可以表示为(if (f[1]==0) f[2]=1;)反过来也一样，即若B为女生，A一定不是。同理，“A与C性别相同”这句话就可以表示为(f[3]=f[1])。而这，就是一道最简单的2-sat问题。
那么在此基础上，我们就可以开始分析2-sat了。
概念
SAT是适定性(Satisfiability)问题的简称 。一般形式为k-适定性问题，简称 K-SAT。
可以证明，当(K>2)时，K-SAT是NP完全的。因此一般讨论的是k=2的情况，即2-SAT问题。
我们通俗的说，就是给你n个变量(a_i)，每个变量能且只能取0/1的值。同时给出若干条件，形式诸如((not)a_i) opt ((not)a_j = 0/1)，其中opt表示(and,or,xor)中的一种
而求解2-SAT的解就是求出满足所有限制的一组a
如何求解2-sat
我们发现，每一个条件如上题中“如果A为女生，B一定不是女生”我们可以考虑将A与B拆点，拆为A为女（(a_0)）、A为男（(a_1)）、B为女（(a_2)）和B为男（(a_3)）。那么这个条件我们就可以将(a_1)向(a_4)连一条单向边，(a_3)向(a_2)连一条单向边。那么当我们发现它成为了环时，准确来说是当(a_i)和(a_{i+1})在同一个环中，也就是说某人（hzr）既要当男生又要当女生时，显然是不成立的，此时是无解的。若没有出现这种情况，就说明存在这样一组解。
我们可以举一些简单的例子来总结下连边的规律（用i′表示i的反面）：
(i,j)不能同时选：选了(i)就要选(j′)，选(j)就要选(i′)。故(i ightarrow j′),(j ightarrow i′)。一般操作即为(a_i) ^ (a_j=1)
(i,j)必须同时选：选了(i)就要选(j)，选(j)就要选(i)。故(i ightarrow j),(j ightarrow i)。一般操作即为(a_i) ^ (a_j)=0
(i,j)任选（但至少选一个）选一个：选了(i)就要选(j′)，选j就要选(i′)，选(i′)就要选(j)，选(j′)就要选(i)。故(i ightarrow j′),(j ightarrow i′),(i′ ightarrow j),(j′ ightarrow i)。一般操作即为(a_i) ^ (a_j)=1
(i)必须选：直接(i′)→(i)，可以保证无论怎样都选(i)。一般操作为给出的(a_i=1)或(a_i) & (a_j=1)
解法1——DFS
- 对于每个当前不确定的变量(a_i)，令(a_i=0)然后沿着边DFS访问相连的点。
- 检查如果会导致任意一个(j)与(j′)都被选，那么撤销。否则令a_i=0
- 否则令(a_i=1)，重复2。如果还不行就无解。
- 继续考虑下一个不确定的变量
这里贴一下DFS的板子
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+5;
struct edge{
int nex,to;
}e[maxn];
int fl[maxn],n,m,beg[maxn],tot,s[maxn],cnt;
int read() {
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')f=-f;ch=getchar();}
while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void add(int x,int y) {
e[++tot]=(edge){beg[x],y};
beg[x]=tot;
}
bool dfs(int now) {
if (fl[now^1]) return true;
if (fl[now]) return false;
s[++cnt]=now;fl[now]=1;
for (int i=beg[now];i;i=e[i].nex) {
int nex=e[i].to;
if (dfs(nex)) return true;
}
return false;
}
int main() {
n=read();m=read();
for (int i=1;i<=m;i++) {
int x=read()-1,u=read(),y=read()-1,v=read();
add(x*2+1-u,y*2+v);
add(y*2+1-v,x*2+u);
}
for (int i=0;i<n*2;i+=2) {
cnt=0;
if (dfs(i)) {
while(cnt) fl[s[cnt--]]=0;
if (dfs(i+1)) {
puts("IMPOSSIBLE");
return 0;
}
}
}
puts("POSSIBLE");
for (int i=0;i<n;i++) {
if (fl[i*2]) cout<<0<<' ';
else cout<<1<<' ';
}
return 0;
}
//复杂度（O(n+m)）
解法2——SCC
考虑我们上面的判断有无解的情况，我们想到完全可以借助SCC来判断两个点是否互相到达。
那么我们先缩点，如果(i)与(i′)在同一SCC里那么显然无解。
否则选择i与i′中拓扑序较大的一个就可以得到一组可行解。
不是很常用（主要是一般题目的数据范围都不需要），用来判可行性比较好。