AcWing 2402. 2-SAT 问题
原题链接
中等
作者:
溪染
,
2021-01-22 15:59:21
,
所有人可见
,
阅读 779
#include<bits/stdc++.h>
using namespace std;
const int N=4e6+7;
struct oppo{
int to,nex;
}rod[N];
int head[N],tot;
void add(int from,int to)
{
rod[++tot].to=to;
rod[tot].nex=head[from];
head[from]=tot;
}
int n,m;
int dfn[N],low[N],all;
int in[N];
int stk[N],hh;
int clo[N],clo_tot;
void dfs(int x)
{
dfn[x]=low[x]=++all;
stk[++hh]=x;in[x]=1;
for(int i=head[x];i;i=rod[i].nex){
int to=rod[i].to;
if(!dfn[to]){
dfs(to);
low[x]=min(low[to],low[x]);
}else if(dfn[to]&&in[to])
low[x]=min(low[x],dfn[to]);
}
if(low[x]==dfn[x]){
++clo_tot;
while(stk[hh+1]!=x){
clo[stk[hh]]=clo_tot;
in[stk[hh]]=0;
hh--;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,a,y,b;
scanf("%d%d%d%d",&x,&a,&y,&b);
x*=2;y*=2;
add(x|(!a),y|b);//若xa不选,yb必选
add(y|(!b),x|a);//若yb不选,xa必选
}
for(int i=2;i<=2*n+1;i++)
if(!dfn[i])
dfs(i);
for(int i=1;i<=n;i++)
if(clo[i*2]==clo[i*2+1]){
puts("IMPOSSIBLE");
return 0;
}
puts("POSSIBLE");
for(int i=1;i<=n;i++)
cout<<(clo[i*2]>clo[i*2+1])<<" ";
return 0;
}