模板：2-SAT

实际上是每个变量有两个状态把
然后扩展开来
注意每个数组开原来的二倍
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=1000010;
 7 int head[maxn<<1], cnt;
 8 int dfn[maxn<<1], low[maxn<<1], st[maxn<<1];
 9 int scc[maxn<<1];//强连通分量的拓扑序
10 bool in[maxn<<1];
11 int m, n, top, num, ct;
12 struct edge{
13     int to, next;
14 }a[maxn<<2];
15 void add(int from, int to){
16     cnt++;
17     a[cnt].to=to;
18     a[cnt].next=head[from];
19     head[from]=cnt;
20 }
21 void tarjan(int u){//缩点
22     low[u]=dfn[u]=++num;
23     st[top++]=u;
24     in[u]=true;
25     for(int i=head[u]; i; i=a[i].next){
26         int v=a[i].to;
27         if(!dfn[v]){
28             tarjan(v);
29             low[u]=min(low[u],low[v]);
30         }
31         else if(in[v]) low[u]=min(low[u],dfn[v]);
32     }
33     if(low[u]==dfn[u]){
34         int v;
35         ct++;
36         do{
37             v=st[--top];
38             in[v]=false;
39             scc[v]=ct;
40         }while(u!=v);
41     }
42 }
43 bool sat(){
44     for(int i=1; i<=n*2; i++){
45         if(!dfn[i]) tarjan(i);
46     }
47     for(int i=1; i<=n; i++){
48         if(scc[i]==scc[i+n]) return false;//如果两个在同一个，也就意味着自相矛盾不存在
49     }
50     return true;
51 }
52 int main(){
53     scanf("%d%d",&n,&m);
54     for(int i=1; i<=m; i++){
55         int a, b, av, bv;
56         scanf("%d%d%d%d",&a,&av,&b,&bv);
57         int na=av^1, nb=bv^1;//a表示条件a选0的情况，a+n表示条件a选1的情况。 
58         add(a+na*n, b+bv*n);//相应建图方式，具体不理解可以手动推一下
59         add(b+nb*n, a+av*n);
60     }
61     if(sat()){
62         printf("POSSIBLE
");
63         for(int i=1; i<=n; i++)
64             printf("%d ",scc[i]>scc[i+n]);//反着的拓扑序，如果大于成立则说明1其实是拓扑序大的，小于成立反之
65     }
66     else printf("IMPOSSIBLE");
67     return 0;
68 }
注意每个数组开