2-SAT问题

只会做模板题嘤

所谓$2-sat$问题，其实是$k-sat$问题的一种特殊形式。

以下是$k-sat$问题的粗略解释。

一共有一些人 每人有$k$个不同的要求 现在求一种方案使每个人的要求都能被至少满足一个（这个解释好像不太严谨吧

$2-sat$问题更严谨的解释：

有$n$个布尔变量$x_1$~$x_n$,另有$m$个需要满足的条件，

每个条件的形式都是“$x_i$为$true/false$或$x_j$为$true/flase$”。

比如“$x_1$为真或$x_3$为假”、“$x_7$为假或$x_2$为假”。$2-sat$问题的目标是给每个变量赋值使得所有条件得到满足。

那么，我们发现所有的条件其实可以书写成$a\vee b$的形式。

接着，我们把它变形就可以得到$\lnot a\rightarrow$ $b \wedge \lnot b \rightarrow a$

为什么呢？因为$a$和$b$两个条件取其中之一满足时，如果$a$不满足，则$b$一定满足。如果$b$不满足，则$a$一定满足。但是a满足不能推出b不满足

所以我们现在可以建一个有向图惹。如果$a$与$b$相连，则$a$可以推出$b$。

判断IMPOSSIBLE的情况： 先对有向图进行缩点，如果$x$和$\lnot x$在同一个
强连通分量里，那就是不可能的情况。因为同一个强连通分量里的各个点之间都有连接的路径，所以各个布尔值互相都可以推出。这样的话$x$和$\lnot x$就必须同时满足，但显然这是不可能的。所以IMPOSSIBLE

如何求解每个布尔变量的值： 显然，当我们进行缩点之后，原本的图就变成了一张$DAG$，那么此时我们就可以进行拓扑排序惹。有一点很显然就是拓扑序靠后的一定是有拓扑序靠前的推出来的。所以如果一个布尔变量满足，则拓扑序比他靠后的布尔变量一定也满足。所以我们只要判断每个$x$和$\lnot x$的拓扑序就行了，如果$x$的拓扑序比$\lnot x$的拓扑序靠后，那么此布尔变量取$1$，否则取$0$。

#include <iostream>
#include <cstdio>
using namespace std;
#define N 2000050
#define M 1000050
int head[N],num,low[N],dfn[N],dfx,co[N],col,st[N],top,n,m,val[N];
struct node
{
    int next,to;
}tu[M*2];
void addedge(int u,int v)
{
    tu[++num]=(node){head[u],v};
    head[u]=num;
}
void tarjan(int u)
{
    low[u]=dfn[u]=++dfx;
    st[++top]=u;
    for(int i=head[u];i;i=tu[i].next)
    {
        int v=tu[i].to;
        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()
{
    scanf("%d%d",&n,&m);
    int a,b,c,d;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        addedge(a+(b^1)*n,c+d*n);
        addedge(c+(d^1)*n,a+b*n);
    }    
    for(int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)if(co[i+n]==co[i]){printf("IMPOSSIBLE");return 0;}
    printf("POSSIBLE\n");
    for(int i=1;i<=n;i++)printf("%d ",co[i]>co[i+n]);
}