0. 前言

因为之前一篇写的太烂了，没有搞清楚主次关系导致云里雾里，以至于后人（没错就是我自己）根本看不懂，所以本篇于2025.4.22重写。

你需要知道芝士：

Tarjan求有向图强联通分量
基础图论建模芝士
命题的概念及反命题（初中内容）

1. 2-SAT概念及求法

1.1 概念

这个我们需要好好说这个概念，所以我们对于 “2-SAT” 这个名词我们做一下辨析。

SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，即 k-SAT。

什么，看不懂？没关系因为这个k-SAT问题当 $k>2$ 的时候是NP完全问题，只能暴力求解，但是当 $k=2$ 的2-SAT问题我们可以好好玩。

对于2-SAT问题通俗的说，就是给你 $n$ 个变量 $X_i$ ，每个变量只能取 0或1，同时给定若干条件，形如：

(\neg) X_{i}\oplus (\neg)X_{j}=0 /1

其中 $\neg X_i$ 表示 $X_i$ 这个命题的反命题。其中 $\oplus$ 代表的操作有与，或，异或操作中的一种。

其实不难发现我们在求解2-SAT问题，如果我们发现这个问题的“方程组”有解，那么其实解有许多组，但是我们只需要求出1组解即可。

1.2 2-SAT求解

所以怎么求解呢？一个显然的想法是暴力枚举，但是这个复杂度太炸裂了（其实也不算太炸裂www），怎么做？

我们发现与，或，异或操作一定有不同真命题与反命题之间约束的关系…图论？

没错其实对于这类问题我们可以建立图论模型来去解决，虽然两两bool变量的关系有很多，但是可以都归属以下三种关系：

\begin{aligned} \neg X_{i} & \vee X_{j} \\ \neg X_{i}& \vee \neg X_{j}\\ X_{i}& \vee X_j \end{aligned}

其中， $\vee$ 符号表示或的关系。其实不难得到如果左边不成立那右边必须成立，于是我们可以对于 $X_{i},\neg X_{i},X_{j},\neg X_j$ 这四个变量我们可以用四个不同的变量：

$X_{i}\rightarrow T_i$
$X_{j}\rightarrow T_j$
$\neg X_{i}\rightarrow F_i$
$\neg X_{j}\rightarrow F_j$

那么我们可以这么连边：
对于第一个式子，如果我们让 $X_i$ 成立（ $\neg X_i$ 不成立），那么 $X_j$ 必须成立，如果 $\neg X_j$ 成立那么 $\neg X_i$ 必须成立，下面同理：

公式	建边(同时建边代表与)
$\neg X_{i} \vee X_j$	$T_{i}\rightarrow T_{j},F_{j}\rightarrow F_{i}$
$\neg X_{i} \vee \neg X_{j}$	$T_{i}\rightarrow F_{j},T_{j}\rightarrow F_{i}$
$X_{i} \vee X_{j}$	$F_{i}\rightarrow T_{j},F_{j} \rightarrow T_{i}$

有没有发现什么？其实建边中都是假设一个变量不成立，那么另一个变量必定成立，通过像这样限定两个变量建2条边就可以限定了。

那我们建立好图：

这里变量名有所改变，但是不难发现的一点就是，如果 $\neg a,b$ 在一个强联通分量那么解肯定是一样的。但是，例如 $a,\neg a$ 在同一个强联通分量，那么必定无解，因为这两个必须选一个但是如果在一个强联通分量，那么必定无解，反之一定有解。

那怎么构造解呢？在一个强联通分量如果我们确定任意一个变量的初始赋值，那么这里面其他所有变量的赋值都确定，这启发我们缩点。其次互为逆否命题会成对出现（对称性），所以一个零出度点的否命题（否命题的否命题是真命题）一定有出边，选有出点的一定会影响后面的，而选择零初度点的不会影响。

于是我们可以有一个基本思想就是：自底向上走拓扑排序，不断尝试选择零出度点。

但是tarjan中SCC的一个存储特点就是刚好是反拓扑序（自底向上的），所以只需要对比 $X_i$ 和 $\neg X_i$ 两个所属于的强联通分量编号谁更小，更小的拓扑序越大，越优。

P4782 【模板】2-SAT

这里我们用 $i \rightarrow X_{i},i+n \rightarrow \neg X_{i}$

那么代码如下：

#include<iostream>
#include<vector>
using namespace std;
const int MN=2*1e6+15;
int n,m,dfn[MN],low[MN],vdcc[MN],tot,dcc;
vector<int> adj[MN];
bool vis[MN];
int s[MN],top;
void tarjan(int u){
    low[u]=dfn[u]=++tot;
    s[++top]=u;
    vis[u]=1;
    for(int i=0;i<adj[u].size();i++){
        int v=adj[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        dcc++;
        int t;
        while (s[top]!=u)
        {
            vdcc[s[top]]=dcc;
            vis[s[top]]=0;
            top--;
        }
        vdcc[s[top]]=dcc;
        vis[s[top]]=0;
        top--;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int xi,a,xj,b;
        cin>>xi>>a>>xj>>b;
        int ni=xi+n,nj=xj+n;
        if(a==0&&b==0){
            adj[ni].push_back(xj);//a=1则b=0
            adj[nj].push_back(xi);//b=1则a=0
        }
        if(a==1&&b==0){
            adj[xi].push_back(xj);//a=0则b=0
            adj[nj].push_back(ni);//b=1则a=1
        }
        if(a==0&&b==1){
            adj[ni].push_back(nj);//a=1则b=1
            adj[xj].push_back(xi);//b=0则a=0
        }
        if(a==1&&b==1){
            adj[xi].push_back(nj);//a=0 b=1
            adj[xj].push_back(ni);//b=0 a=1
        }
    }
    for(int i=1;i<=n*2;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(vdcc[i]==vdcc[i+n]){
            cout<<"IMPOSSIBLE";
            return 0;
        }
    }
    cout<<"POSSIBLE"<<endl;
    for(int i=1;i<=n;i++){
        //强联通分量编号越小 -> 拓扑序越大 -> 越优
        cout<<(vdcc[i]>vdcc[i+n])<<" ";
    }
    return 0;
}

2. 例题

2.1 P4171 满汉全席

我们可以拆成2个点，一个是汉式，一个是满式。

于是就变成了正反命题，就可以2-SAT了。
关于式子看代码。

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int MN=2048;
int k,n,m,tot,ecc,dfn[MN],low[MN],color[MN],s[MN],top;
vector<int> adj[MN];
bool vis[MN];
void tarjan(int u){
    low[u]=dfn[u]=++tot;
    vis[u]=1;
    s[++top]=u;
    for(int i=0;i<adj[u].size();i++){
        int v=adj[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ecc++;
        int p;
        do
        {
            p=s[top--];
            color[p]=ecc;
            vis[p]=0;
        } while(p!=u);
        
    }
}
int main(){
    cin>>k;
    while (k--)
    {
        top=tot=ecc=0;
        cin>>n>>m;
        for(int i=1;i<MN;i++){
            dfn[i]=low[i]=color[i]=0;
            adj[i].clear();
        }
        char p1,p2;
        int a,b,xa,xb;
        //m->0 h->1
        for(int i=1;i<=m;i++){
            cin>>p1>>a>>p2>>b;
            int na=a+n,nb=b+n;
            if(p1=='m'&&p2=='h'){//a=0 b=1
                adj[b].push_back(a);//b=0 a=0
                adj[na].push_back(nb);//a=1 b=1
            }
            if(p1=='h'&&p2=='h'){//a=1 b=1
                adj[a].push_back(nb);
                adj[b].push_back(na);
            }
            if(p1=='h'&&p2=='m'){//a=1 b=0
                adj[a].push_back(b);
                adj[nb].push_back(na);
            }
            if(p1=='m'&&p2=='m'){// a=0 b=0
                adj[nb].push_back(a);
                adj[na].push_back(b);
            }
        }
        for(int i=1;i<=2*n;i++){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        bool flag=0;
        for(int i=1;i<=n;i++){
            if(color[i]==color[i+n]){
                cout<<"BAD"<<endl;
                flag=1;
                break;
            }
        }
        if(!flag) cout<<"GOOD"<<endl;
    }
    
    return 0;
}

P6378 Riddle

$n$ 个点 $m$ 条边的无向图被分成 $k$ 个部分。每个部分包含一些点。
请选择一些关键点，使得每个部分恰有一个关键点，且每条边至少有一个端点是关键点。
$1\le k,w\le n\le 10^6$ ， $\sum w=n$ ， $1\le a,b\le n$ ， $0\le m\le 10^6$ 。

初始观察这个题我们其实发现不出来这个和2-SAT有什么关系，但是我们发现一个点，我们边至少有一个端点是关键点。而且这些部分中只能选1个，剩下全都不选。很像2-SAT的真否命题。

那么我们的命题就是选或不选，对于第一个条件，其实就是 $\neg u \rightarrow v,\neg v \rightarrow u$ 。

而对于第二个条件，就是枚举组内的点暴力连边，选定一个成立后对组内其他节点暴力连否命题的边，那么这个题就做完…了？

这样暴力连边的复杂度是 $O(n^2)$ ，不仅时间炸空间也会炸掉，怎么办？

借用以下阴阳八卦大佬的图：

我们暴力连边的边如下：

这样连边的分数我们只能拿到92分。怎么优化？关键在于怎么优化这种建图方式，第一种是优化不了了只能优化第二种。我们观察以下：

1向4，6，8连边。
3向2，6，8连边。
5向2，4，8连边。
7向2，4，6连边。

我们新建一些点作为这个点的分身：

转移以下边：

我们利用上面的方式，我们其实不难发现9-16，10-16，11-16，可以直接转成9-10-11-16这样连边，而且这样连边甚至9-15,9-16都不用连了！这样连就可以得到这张图。

唉不对啊，1-9-14-13-2这是什么，我们修改以下，把9-14改为9-4，把10-13改为3-13。一系列操作有：

这种优化方式叫做 前缀优化建图，通过类似于前缀和的优化操作来建图。

有的人会说线段树优化建图，请自己想想两个建图方式实质上是不是类似。

故代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MN=8e6+15;
int n,m,k,dfn[MN],low[MN],vdcc[MN],tot,dcc; 
// dfn: DFS序, low: Tarjan算法中的low值, 
// vdcc: 强连通分量编号, tot: dfn时间戳, dcc: 强连通分量计数器
vector<int> adj[MN],gp[MN]; //gp: 存储每个部分(题意中的部分)的点
bool vis[MN];
int s[MN],top;

void tarjan(int u){
    // tarjan求强联通
    low[u]=dfn[u]=++tot;
    s[++top]=u;
    vis[u]=1;
    for(auto v:adj[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        dcc++;
        int p;
        do
        {
            p=s[top--];
            vdcc[p]=dcc;
            vis[p]=0;
        } while (p!=u);
    }
}

// 以下注释中
// ¬u表示u的否定，即u+n
// u的前缀辅助点，即u+2n
// u的后缀辅助点，即u+3n
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        int fu=u+n,fv=v+n;
        adj[fu].push_back(v); // 添加边¬u → v
        adj[fv].push_back(u); // 添加边¬v → u
    }
    for(int i=1;i<=k;i++){
        int num;
        cin>>num;
        for(int j=1;j<=num;j++){
            int p;
            cin>>p;
            gp[i].push_back(p);
            adj[p].push_back(p+2*n); // 添加边 p → p+2n（前缀变量）
            adj[p+3*n].push_back(p+n); // 添加边 p+3n → ¬p（后缀变量）
        }
        for(int j=1;j<gp[i].size();j++){
            int d1=gp[i][j-1],d2=gp[i][j]; // 前一个点和当前点

            adj[d1+2*n].push_back(d2+2*n); // 添加边 d1+2n → d2+2n（前缀传递）
            adj[d2+3*n].push_back(d1+3*n); // 添加边 d2+3n → d1+3n（后缀传递，可以看图理解）

            adj[d1+2*n].push_back(d2+n); // 添加边 d1+2n → ¬d2（前缀已选，d2不可选）
            adj[d2].push_back(d1+3*n); // 添加边 d2 → d1+3n（选d2，后缀必须选到d1）
        }
    }

    for(int i=1;i<=n*4;i++){
        if(!dfn[i]) tarjan(i);
    }

    for(int i=1;i<=n;i++){
        if(vdcc[i]==vdcc[i+n] || vdcc[i+2*n]==vdcc[i+3*n]){ 
            // 如果i和¬i在同一分量，或前缀和后缀变量在同一分量则环无解
            cout<<"NIE";
            return 0;
        }
    }
    cout<<"TAK";
    return 0;
}