2-SAT模板

主要作为参考代码.

---

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,x1,x2,y1,y2;
int dfn[3000010],low[3000010],vis[3000010],clr[3000010],stc[3000010],top=0,tot=0,tim=0;
int head[3000010],cnt=0;
struct Edge{
    int v,nxt;
}e[3000010];
void addEdge(int u,int v){
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void tarjan(int u){
    dfn[u]=low[u]=++tim;
    stc[++top]=u;vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        if(!dfn[e[i].v]){
            tarjan(e[i].v);
            low[u]=min(low[u],low[e[i].v]);
        }
        else if(vis[e[i].v]){
            low[u]=min(low[u],dfn[e[i].v]);
        }
    }
    if(dfn[u]==low[u]){
        tot++;
        while(stc[top+1]!=u){
            clr[stc[top]]=tot;
            vis[stc[top--]]=0;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
        if(x2==0&&y2==0){
            addEdge(x1,y1+n);
            addEdge(y1,x1+n);
        }
        if(x2==1&&y2==1){
            addEdge(x1+n,y1);
            addEdge(y1+n,x1);
        }
        if(x2==0&&y2==1){
            addEdge(x1,y1);
            addEdge(y1+n,x1+n);
        }
        if(x2==1&&y2==0){
            addEdge(x1+n,y1+n);
            addEdge(y1,x1);
        }
    }
    for(int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++){
        if(clr[i]==clr[i+n]){
            printf("IMPOSSIBLE
");
            return 0;
        }
    }
    printf("POSSIBLE
");
    for(int i=1;i<=n;i++){
        if(clr[i]>clr[i+n])printf("0 ");
        else printf("1 ");
    }
    printf("
");
    return 0;
}