2-SAT 学习笔记

· · 算法·理论

优质博客

panyf的博客

基础模型

给出若干个 bool 型的限制条件：若 a 为 1/0，则 b 为 1/0。要求判断是否有合法解且输出，那么就是我们的 2-SAT 登场了！

解决思路

考虑将限制条件都转换成图论中的连边，对于若 1 条件成立则 2 条件成立或不成立，一般应用到拆点的思想。类似于分层最短路，将一点拆成多个状态点，在模型中对于结点 i，可以认为其为 0，然后拆出 i+n 点表示其为 1，那么若 a=1 则 b=0 的条件就可以表示为一条 i+n \to j 的边。得到 2-SAT 的第一条规律：若一条有向边的起点成立，则终点一定成立。

如果拆点建图之后同一点会产生矛盾的两个状态点在同一个 SCC 中，显然不合法。因此我们可以称其中一个为合法点，另一个为不合法点，那么如果有非法点 u，合法点 v，且原图为 DAG，对于这样的连边 u\to v，u 的拓扑序必然小于 v 的拓扑序，因为拓扑遍历一定会先经过入度更小的点。所有可以得出第二条规律：合法点的拓扑序必然大于非法点。

那如果原图不是 DAG 呢，直接上缩点就好了嘛。每一个强连通分量都会成为一个点，只要强连通分量其中一个点合法，则其它点必然都合法。那么在新图中，一个点的合法点所在的强连通分量的编号小于非法点。可以有这种方式理解：如果跑完 Tarjan 缩点之后呈现出的拓扑序更大，在 Tarjan 会更晚被遍历到，就会更早地被弹出栈而缩点，编号会更小。

接下来为判断是否存在合法解，如果同一点的两个矛盾的状态点存在于同一个强连通分量中，那么整个问题无解。如果两个点之间不存在任何路径，即使有有向边，那么选择 SCC 编号小的点就好了。

例题探究

1.模板\ Code:

  #include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define int long long
#define re register
#define For(i,l,r) for(re int i=l;i<=r;i++)
#define Rep(i,l,r) for(re int i=l;i>=r;i--)
#define ls(c) c<<1
#define rs(c) c<<1|1
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=3e6+5;
inline void fast(){
       ios::sync_with_stdio(false);
       cin.tie(0);cout.tie(0);
}
inline void read(int &x){
       x=0;int f=1;
       char c=getchar();
       while(!isdigit(c)){
            if(c=='-') f=-1;
            c=getchar();
       }while(isdigit(c)){
            x=x*10+c-'0';
            c=getchar();
       }x*=f;
}
inline void write(int x){
       if(x<0){x=-x;putchar('-');}
       if(x>9) write(x/10);
       putchar(x%10+'0');
}int n,m,i,a,j,b;
vector<int> e[N];
int dfn[N],low[N],s[N],tp,ins[N];
int sc,scc[N],dfncnt;
inline void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    s[++tp]=u;ins[u]=1;
    for(int j=0;j<e[u].size();j++){
        int v=e[u][j];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }if(dfn[u]==low[u]){
        ++sc;
        while(s[tp]!=u){
            ins[s[tp]]=0;
            scc[s[tp]]=sc;
            --tp;
        }
        ins[s[tp]]=0;
        scc[s[tp]]=sc;
        --tp;
    }
}
signed main(){
    fast();
    cin>>n>>m;
    For(k,1,m){
        cin>>i>>a>>j>>b;
        //+n=1
        if(a&&b){
            e[i].push_back(j+n);
            e[j].push_back(i+n);
        }else if(a&&!b){
            e[i].push_back(j);
            e[j+n].push_back(i+n);
        }else if(!a&&b){
            e[i+n].push_back(j+n);
            e[j].push_back(i);
        }else if(!a&&!b){
            e[i+n].push_back(j);
            e[j+n].push_back(i);
        }
    }
    For(k,1,n*2){
        if(!dfn[k]) tarjan(k);
    }
    For(k,1,n){
        if(scc[k]==scc[k+n]){
            cout<<"IMPOSSIBLE\n";
            return 0;
        }
    }
    cout<<"POSSIBLE\n";
    For(k,1,n){
        cout<<(scc[k]>scc[k+n])<<' ';
    }
    return 0;
}

2.简单题(套模板) 直接根据题目条件建边即可。\ Code:

#include <iostream>
#include <queue>
#include <set>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
template<typename type>
inline void write(type x)
{
    x<0?x=-x,putchar('-'):0;
    static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
}
inline char read(char &ch){return ch=getchar();}
inline char write(const char &ch){return putchar(ch);}
template<typename type,typename ...T>
inline void read(type &x,T&...y){read(x),read(y...);}
template<typename type,typename ...T>
inline void write(type x,T...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
const int N=5e5+5,M=1005;
int T,n,m;
string a,b;
vector<int> e[N*2];
void add(int a,int b){
    e[a].push_back(b);
}
int dfn[N],low[N],dfncnt;
int s[N],tp,scc[N],sc;
bool ins[N];
void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    s[++tp]=u;ins[u]=1;
    for(auto v:e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++sc;
        while(s[tp]!=u){
            ins[s[tp]]=0;
            scc[s[tp]]=sc;
            --tp;
        }
        ins[s[tp]]=0;
        scc[s[tp]]=sc;
        --tp;
    }
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
#endif
    cin>>T;
    while(T--){
        cin>>n>>m;
        //i han i+n man
        fill(dfn+1,dfn+2*n+1,0);
        fill(low+1,low+2*n+1,0);
        fill(ins+1,ins+2*n+1,0);
        dfncnt=tp=sc=0;
        for(int i=1;i<=n*2;i++) e[i].clear();
        for(int i=1;i<=m;i++){
            cin>>a>>b;
            int A=0,B=0;
            for(int j=1;j<a.size();j++) A=A*10+a[j]-'0';
            for(int j=1;j<b.size();j++) B=B*10+b[j]-'0';
            if(a[0]=='h'){
                if(b[0]=='h'){//h h
                    add(A+n,B);
                    add(B+n,A);
                }else{//h m
                    add(A+n,B+n);
                    add(B,A);
                }
            }else{
                if(b[0]=='h'){//m h
                    add(A,B);
                    add(B+n,A+n);
                }else{//m m
                    add(A,B+n);
                    add(B,A+n);
                }
            }
        }
        for(int i=1;i<=2*n;i++){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(scc[i]==scc[i+n]) flag=true;
        }
        cout<<(flag?"BAD\n":"GOOD\n");
    }
    return 0;
}