P4782

发表于 分类于
【模板】2-SAT 问题

【模板】2-SAT 问题

命题 $a$ 命题 $b$ 可以转化为 $\lnot a$ 则 $b$ 以及 $\lnot b$ 则 $a$。

建图跑个 Tarjan，若 $a$ 和 $\lnot a$ 在同一个 SCC 内说明该问题不可能成立。

反之我们需要找可行解。

SCC 缩点之后，显然出度为 $0$ 的点是满足之后条件限制最少的，又因为该问题此时一定有解，所以按照缩点后反图的拓扑序来确定答案一定是一组合法解。

但是直接求拓扑序比较麻烦，我们实际上给 SCC 标过号，根据这个编号我们就能确定一对命题 $a$ 和 $\lnot a$ 的拓扑关系。

显然编号越小越应该优先满足，然后这样确定下来就完事了。

时间复杂度 $O(n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}

const ll N=2e6;

ll n,m,tot,cnt,num,top;
ll val[N+5],ver[N+5],nxt[N+5],head[N+5],c[N+5];
ll st[N+5],dfn[N+5],low[N+5];
bool inst[N+5];

inline void Tarjan(ll x) {
  dfn[x]=low[x]=++num;st[++top]=x;inst[x]=1;
  for(ll i=head[x];i;i=nxt[i]) {
    if(!dfn[ver[i]]) {Tarjan(ver[i]);low[x]=min(low[x],low[ver[i]]);}
    else {if(inst[ver[i]]) low[x]=min(low[x],dfn[ver[i]]);}
  }
  if(dfn[x]==low[x]) {
    cnt++;
    do{inst[st[top]]=0;c[st[top]]=cnt;}while(x!=st[top--]);
  }
}

inline void Addedge(ll u,ll v) {
  ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

int main() {

  n=read();m=read();

  for(ll i=1;i<=m;i++) {
    ll x,y,p,q;
    x=read();p=read();y=read();q=read();
    Addedge(x+(1-p)*n,y+q*n);Addedge(y+(1-q)*n,x+p*n);
  }

  for(ll i=1;i<=n*2;i++) {if(!dfn[i]) Tarjan(i);}

  ll flg=0;
  for(ll i=1;i<=n;i++) {if(c[i]==c[i+n]) {flg=1;break;}}

  if(flg) {printf("IMPOSSIBLE\n");}
  else {
    printf("POSSIBLE\n");
    for(ll i=1;i<=n;i++) {
      val[i]=c[i]>c[i+n];writes(val[i]);
    }
  }

  return 0;
}