2-SAT

luckydrawbox · 2023-08-29 23:20:09 · 个人记录

需要连通性相关中的强联通分量缩点。

函数

代码

void Add(int x,int a,int y,int b){
    //if(x=a)y=b
    G1.add(x+a*n,y+b*n);
    G1.add(y+(1-b)*n,x+(1-a)*n);
}
bool _2sat(){
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        if(col[i]==col[n+i])
            return 0;
    return 1;
}