P4782 【模板】2-SAT 问题

Luogu4782

建边时,如果是a,那必须是b,就建a->b

如果\(i\)和\(i+n\)在同一个强连通分量里就矛盾了，如果都在不同的强连通分量则有解

假设\(ctg[i]<ctg[i+n],\)如果选\(i+n\)这个状态,那就会影响到\(i\)即必须选\(i\)这个状态,就矛盾了,所以要选\(ctg[]\)小的状态

总之,按影响正序建边,输出(ctg[]较小则真)

#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=2e6+5;
const int MAXM=2e6+5;

struct Edge{
    int v,next;
}e[MAXM];
int first[MAXN],Ecnt=0;
inline void Add_edge(int u,int v){
    e[++Ecnt]=(Edge){v,first[u]};
    first[u]=Ecnt;
}

int low[MAXN],dfn[MAXN],ctg[MAXN],st[MAXN];
bool instk[MAXN];
int n,m,top,ctgn,idx;

inline void tarjan(int u){
    low[u]=dfn[u]=++idx;
    st[++top]=u;
    for(int i=first[u];i;i=e[i].next){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!ctg[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        ctg[u]=++ctgn;
        while(st[top]!=u)
            ctg[st[top]]=u;
        top--;
    }
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int a=read(),va=read(),b=read(),vb=read();
        Add_edge(a+n*va,b+n*(vb^1));
        Add_edge(b+n*vb,a+n*(va^1));
    }
    for(int i=1;i<=n<<1;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        if(ctg[i]==ctg[i+n]){
            printf("IMPOSSIBLE\n");
            return 0;
        }
    printf("POSSIBLE\n");
    for(int i=1;i<=n;i++)
        printf("%d ",ctg[i]<ctg[i+n]);//如果选i没有后继影响就选i,即真
}

P4782 【模板】2-SAT 问题

原文：https://www.cnblogs.com/lizehon/p/10464174.html