Evanyou Blog 彩带

【模板】2-SAT问题

题目背景

2-SAT 问题模板

题目描述

有n个布尔变量 $x_1/~x_n$ $$x_i$ 为$true/false$或 $x_j$ 为$true/false$”。比如“ $x_1$ 为真或 $x_3$ 为假”、“ $x_7$ 为假或 $x_2$ 为假”。$2-SAT$ 问题的目标是给每个变量赋值使得所有条件得到满足。$

输入输出格式

输入格式：

第一行两个整数$n$和$m$，意义如体面所述。

接下来$m$行每行$4$个整数 $i a j b$，表示“ $x_i$ $$x_j$ 为$b$”($a,bin {0,1}$)$

输出格式：

如无解，输出“IMPOSSIBLE”（不带引号）; 否则输出"POSSIBLE"（不带引号),下一行n个整数 $x_1$ ~ $x_n$ $$x_iin {0,1}$），表示构造出的解。$

输入输出样例

输入样例#1：

3 1
1 1 3 0

输出样例#1：

POSSIBLE
0 0 0

说明

1<=n,m<=1e6 , 前3个点卡小错误，后面5个点卡效率，由于数据随机生成，可能会含有（ 10 0 10 0）之类的坑

　　分析：

　　$2-SAT$模板题，特地练下手。

　　经典的$2-SAT$模型就不多说了，需要注意的是每次建图时要注意点之间的关系，一旦关系多起来就容易建图建错。（好吧其实是我自己建图建错了两次233333）

　　Code：

//It is made by HolseLee on 21st Aug 2018
//Luogu.org P4782
#include<bits/stdc++.h>
#define Max(a,b) (a)>(b)?(a):(b)
#define Min(a,b) (a)<(b)?(a):(b)
using namespace std;

const int N=1e6+7;
int n,m,bel[N<<1],scc,idx,dfn[N<<1],low[N<<1];
bool vis[N<<1];
vector<int>e[N<<1];
stack<int>sta;

inline int read()
{
    char ch=getchar();int num=0;bool flag=false;
    while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();}
    while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
    return flag?-num:num;
}

inline void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    sta.push(u);vis[u]=true;
    int v;
    for(int i=0;i<e[u].size();++i){
        v=e[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(dfn[u]==low[u]){
        scc++;
        do{
            v=sta.top();sta.pop();
            vis[v]=false;bel[v]=scc;
        }while(v!=u);
    }
}

int main()
{
    n=read();m=read();
    int a,b,x,y;
    for(int i=1;i<=m;++i){
        a=read(),x=read(),b=read(),y=read();
        e[a+(x^1)*n].push_back(b+y*n);
        e[b+(y^1)*n].push_back(a+x*n);
    }
    for(int i=1;i<=(n<<1);++i)
    if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i)
    if(bel[i]==bel[i+n]){
        printf("IMPOSSIBLE
");
        return 0;
    }
    printf("POSSIBLE
");
    for(int i=1;i<=n;++i){
        printf("%d ",(bel[i]>bel[i+n]));
    }
    return 0;
}