众所周知，2-SAT是判断一组逻辑关系是否可能成立的重要算法，适用范围十分广泛。

那么2-SAT是怎么一回事呢，下面就让小编带大家一起了解一下吧

2-SAT是什么？能吃吗（期待

2-SAT是2-Satisfiability（双重可能性的可实现性问题）的简称~~（英语蒟蒻落泪）~~。

然而wtcl，所以这个定义我还是看不懂（摊手）

于是让我们举个生活中栗子🌰康康

AKIOI的奆佬zxy和他的好 朋 友们要一起上一样的选修课，可供选择的有数学，物理，化学，信息，道法等科目（雾

可奆佬们比较挑剔，都有自己的喜好

	奆佬的要求
zxy	我爱数学！我一定要上数学！
z**	众所周知，学不好数学就一定学不好物理（大雾。所以，我如果上物理，就一定要上数学！
l**	额，我精 力 有 限，所以我如果上信息就不能上化学了
w**	我对物理和化学一样感兴趣，所以要上他们两个要一起上！

明白了？奆佬们可以去上数学，物理和化学（当然解法不止一种），真的tql（超大雾

这种讨论适定性的问题，便是2-SAT问题

然而怎么可能这么简单呢

题目类型

一般来说，2-SAT问题的形式如下：

给定M个限定条件（通常为与、或、异或中一个），求出是否有满足的选择/排列方式（并输出）

建模方法

终于来到激动人心的环节了（搓手）

对于此类问题，我们一般采取建模（即建图）的方法解决，其中每个点对应一个状态

我们不难看出鉴于每个东西只可能有2种情况（0或1）[2-SAT定义]，可以将每个$a_i$分成两个点，其中1-n为$a_i$取1，n+1-n*2表示$a_i$取0

接下来我们分析一下各种情况对应的建图方式

与

• $a_i$ &&$a_j$ = 1

  即$a_i$、$a_j$均要为真

  所以建边（i+n -> i）和（j+n -> j）

  表示无论如何都要为真，假的也能推出真的（噗嗤）

• $a_i$ &&$a_j$ = 0

即$a_i$、$a_j$中最多有一个为真

所以建边（i -> j+n）和（j -> i+n）

表示j真则i假，i真则j假

或

• $a_i$ ||$a_j$ = 1

  即$a_i$、$a_j$中至少有一个为真

  所以建边（i+n -> j）和（j+n -> i）

  表示j假则i真，i假则j真

• $a_i$ ||$a_j$ = 0

  即$a_i$、$a_j$均为假

  所以建边（i -> i+n）和（j -> j+n）

  表示无论如何都要为假，真的也能推出假的

异或

​ 首先先明确，异或即为比较相不相同，相同为0，不相同为1

• $a_i$ ^$a_j$ = 1

  即$a_i$、$a_j$状态互不相同

  那就简单了，建边（i -> j+n）、（j -> i+n）、（i+n -> j）、（j+n -> i）

• $a_i$ ^$a_j$ = 0

即$a_i$、$a_j$的状态一 模 一 样

所以建边（i -> j）、（j -> i）、（i+n -> j+n）、（j+n -> i+n）

​ 此时我们注意到，异或的连边都是双向边。

​ 这也不难理解，异或在此处是表示相同 / 不同的关系，双方是完全对等的

​ 重点是，此时我们便可以用一个更 简 单的算法来解决这种关系了… 查看答案并查集

好了，讲了这么多，聪明的你能不能写出上图对应的逻辑关系式呢…

解法

普通的有向图，不好操作！

我们缩点后的DAG，好操作！

对于有向图，我们常用的技巧是用Tarjan算法进行缩点，可以缩成一个DAG（有向无环图）

等等

“为什么要缩点啊”

上图

如图，(1,2,3)、(4)、(5,6,7,8)都是一个强连通分量

此时，这三个分量中的每个点都必定状态相同

所以只要有一个条件为真，分量中所有的条件都一定为真，反之亦然

所以如果$(A)$ 和$(\lnot A)$在同一个块里…那不就矛盾了吗？？！

问 题 解 决

再等等

“怎么缩点啊”

前文已提到利用Tarjan算法，这里不再赘述，给出标程。（不会的自己学去

时间复杂度$O(n+m)$ ，是优秀的线性算法

int low[N],dfn[N],scc[N],tot,cnt;
stack<int> st;
void tarjan(int x){
    low[x]=dfn[x]=++tot;//遍历到新点
    st.push(x);//入栈
    for(int i=last[x];i;i=e[i].to){
        int y=e[i].to;//枚举相连的点
        if(!dfn[y]){//没走过
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(!scc[y]){//在栈里
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x]){//形成强连通分量
        cnt++;
        while(st.top()!=x){//出栈
            scc[st.top()]=cnt;
            st.pop();
        }
        scc[st.top()]=cnt;//同上
        st.pop();
    }
}

是不是简单明了小清新呢

方案输出

有时，毒瘤出题人会让我们输出满足题意的方案

如果我们观察缩完点的图，会不难发现它是一个DAG

“DAG好啊” ——某巨佬

DAG一跑拓扑排序不就什么都有了吗…

但是我们在跑Tarjan的时候就有个结论

SCC出栈的顺序即为缩点后图拓扑序的倒序

所以连这步都省了

仔细想一想

拓扑序在后面的一定依赖在前面的

即前面的为真的就一定能推出后面的为真的

而对于点$(A)$ 和$(\lnot A)$，他们的状态必定相反

所以一定是真的在后，假的在前

换成Tarjan中得出栈顺序就得到了：

所在SCC编号小的为真，大的为假

参考代码

bool check(){
    for(int i=1;i<=n;i++){
        if(scc[i]==scc[i+n]) return false;//在同一个强连通分量
    }
    return true;//都不在
}
void output(){
    for(int i=1;i<=n;i++){
        if(scc[i]<scc[i+n]) printf("%d 1\n",i);//编号小的为真
        else printf("%d 0\n",i);
    }
}

例题 & 题解

洛谷P4171 满汉全席

日后再更