题解 P4782 【【模板】2-SAT 问题】

前言

今天上图论课，老师给我们做 2-SAT 、 二分图 、 网络流 的复习。然而我都没预习过！于是学习完 2-SAT 来一波题解啦。

2-SAT是什么

N个 bool 变量 x[1...N]，若干个约束，每个约束形如：x[i]=0/1 和 x[j]=0/1 不能同时成立。问是否存在一个赋值使约束成立。

其他博客里的讲解，都有很多初中生看着苦恼的符号，我就说的通俗一点吧。

校长要给同学们排一节他们想上的课，并且满足每个人的至少一点需求。

甲想要上王老师的数学课。

乙想要上王老师的体育课。

这里面上王老师的课是一个约束，数学课、体育课是一个约束。

怎么解决 2-SAT

前置技能：Tarjan

把一个点分成两份。u -> u+ , u- 。对约束进行分类。这题里具体如下代码。由于分成两个点不大好表示，就表示成 u , u+n。

        if(x==0&&y==0){
            add(a+n,b);
            add(b+n,a);
        }
        else if(x==0&&y==1){
            add(a+n,b+n);
            add(b,a);
        }
        else if(x==1&&y==0){
            add(a,b);
            add(b+n,a+n);
        }
        else if(x==1&&y==1){
            add(a,b+n);
            add(b,a+n);
        }

怎么判断是否有解呢？Tarjan 以后，如果一个点 u 和 u+n 属于一个连通块，那就不可能了。

    for(int i=1;i<=n;i++){
        if(co[i]==co[i+n]){
            puts("IMPOSSIBLE");
            exit(0);
        }
    }

否则即有解。然后输出就很简单了。

    puts("POSSIBLE");
    for(int i=1;i<=n;i++){
        if(co[i]>co[i+n])printf("1 ");
        else printf("0 ");
    }

结合代码

#include <bits/stdc++.h>
using namespace std;

inline int gin(){//快读
    char c=getchar();
    int s=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

const int N=4e6+5;
int n,m,top,num,col,dfn[N],low[N],st[N];
int head[N],ne[N],to[N],co[N],tot; 
//co[i]表示点i属于的连通块，其他数组名为常规

inline void add(int u,int v){//前向星连边，没有边权
    to[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}

void tarjan(int u){//做一遍Tarjan，求出每个点所在的连通块。
    dfn[u]=low[u]=++num;
    st[++top]=u;
    for(int i=head[u],v;i;i=ne[i]){
        v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!co[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        co[u]=++col;
        while(st[top]!=u){
            co[st[top]]=col;
            top--;
        }
        top--;
    }
}

int main(){
    n=gin(),m=gin();
    for(int i=1;i<=m;i++){
        int a=gin(),x=gin();
        int b=gin(),y=gin();
        //分类。还有一种需要推很久的位运算压成两行代码，题解区里有，我是推不出来了。
        if(x==0&&y==0){
            add(a+n,b);
            add(b+n,a);
        }
        else if(x==0&&y==1){
            add(a+n,b+n);
            add(b,a);
        }
        else if(x==1&&y==0){
            add(a,b);
            add(b+n,a+n);
        }
        else if(x==1&&y==1){
            add(a,b+n);
            add(b,a+n);
        }
    }
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++){
        if(co[i]==co[i+n]){
            puts("IMPOSSIBLE");
            exit(0);
        }
    }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++){
        if(co[i]>co[i+n])printf("1 ");
        else printf("0 ");
    }
    return 0;
}