D35【模板】2-SAT

2-SAT问题详解-CSDN博客

2-SAT - OIWiki

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
vector<int>G[N];
int tsp, cnt, dfn[N], low[N], scc[N];
stack<int>stk;bool instk[N];
 
void tarjan(int x)
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);instk[x]=1;
    for(int y:G[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x], low[y]);
        }
        else if(instk[y]) low[x]=min(low[x], dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        cnt++;
        for(int z=-1;z!=x;)
        {
            z=stk.top(); stk.pop(); instk[z]=0;
            scc[z]=cnt;
        }
    }
}
int main()
{
    int n,m;scanf("%d%d", &n, &m);
    for(int i=1,x,y,a,b;i<=m;i++)
    {
        scanf("%d%d%d%d", &x, &a, &y, &b);
        G[x+!a*n].push_back(y+b*n);
        G[y+!b*n].push_back(x+a*n);
    }
    tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(instk,0,sizeof(instk));
    for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++) if(scc[i]==scc[i+n]) {puts("IMPOSSIBLE"); return 0;}
    puts("POSSIBLE");
    for(int i=1;i<=n;i++) printf("%d ",scc[i]>scc[i+n]);
    return 0;
}