[模板]2-SAT问题

本文主要是介绍[模板]2-SAT问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<iostream>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=10010000;
struct Edge{
    int pre,to;
}edge[WR];
int n,m;
int head[WR],tot;
int ipt[WR],low[WR],cnt;
int sze[WR],point,id[WR];
bool instk[WR];
stack<int> s;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void add(int u,int v){
    edge[++tot].pre=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
void tarjan(int u){
    ipt[u]=low[u]=++cnt;
    s.push(u),instk[u]=true;
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
        if(!ipt[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(instk[v]){
            low[u]=min(low[u],ipt[v]);
        }
    }
    if(ipt[u]==low[u]){
        point++;
        int v;
        do{
            v=s.top(),s.pop();
            instk[v]=false;
            sze[point]++;
            id[v]=point;
        }while(u!=v);
    }
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int a=read(),x=read();
        int b=read(),y=read();
        if(x==0&&y==0){
            add(a+n,b);
            add(b+n,a);
        }
        if(x==1&&y==0){
            add(a,b);
            add(b+n,a+n);
        }
        if(x==0&&y==1){
            add(b,a);
            add(a+n,b+n);
        }
        if(x==1&&y==1){
            add(a,b+n);
            add(b,a+n);
        }
    }
    for(int i=1;i<=n*2;i++){
        if(!ipt[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){
        if(id[i]==id[i+n]){
            printf("IMPOSSIBLE\n");
            return 0;
        }
    }
    printf("POSSIBLE\n");
    for(int i=1;i<=n;i++){
        if(id[i]>id[i+n]) printf("1 ");
        else printf("0 ");
    }
    return 0;
}

这篇关于[模板]2-SAT问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！