SAT算法

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+5;
 4 int n,m,a,b,fla,flb,cnt,head[N<<1];
 5 int dfn[N<<1],low[N<<1],vis[N<<1],col[N<<1],scnt,idx;
 6 stack<int> st;
 7 struct edge{
 8     int to,next;
 9 }e[N<<1];
10 inline void addedge(int a,int b)
11 {
12     e[++cnt]={b,head[a]};
13     head[a]=cnt;
14 }
15 void tarjan(int u)
16 {
17     dfn[u]=low[u]=++idx;vis[u]=1;
18     st.push(u);
19     for(int i=head[u];i;i=e[i].next)
20     {
21         if(!dfn[e[i].to]) tarjan(e[i].to),low[u]=min(low[u],low[e[i].to]);
22         else if(vis[e[i].to]) low[u]=min(low[u],dfn[e[i].to]);
23     }
24     if(low[u]==dfn[u])
25     {
26         scnt++;int v=-1;
27         while(v!=u)
28         {
29             v=st.top();st.pop();
30             col[v]=scnt,vis[v]=0;
31         }
32     }
33 }
34 int main()
35 {
36     for(scanf("%d%d",&n,&m);m--;){
37         scanf("%d%d%d%d",&a,&fla,&b,&flb);
38         int aa=fla^1,bb=flb^1;
39         addedge(a+aa*n,b+flb*n);
40         addedge(b+bb*n,a+fla*n);
41     }
42     for(int i=1;i<=2*n;i++)
43         if(!dfn[i]) tarjan(i);
44     for(int i=1;i<=n;i++)
45         if(col[i]==col[n+i]) return puts("IMPOSSIBLE")&0;
46     puts("POSSIBLE");
47     for(int i=1;i<=n;i++) printf("%d%c",col[i]>col[n+i],i==n?‘\n‘:‘ ‘);
48 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1005;
 4 int n,m,a,b,fla,flb,cnt,scnt,idx,flag;
 5 int head[N<<1],dfn[N<<1],low[N<<1],vis[N<<1],col[N<<1];
 6 stack<int> st;
 7 struct edge{
 8     int to,next;
 9 }e[N*N];
10 void init()
11 {
12     memset(head,-1,sizeof(head));
13     memset(dfn,0,sizeof(dfn));
14     memset(vis,0,sizeof(vis));
15     memset(low,0,sizeof(low));
16     cnt=idx=scnt=flag=0;
17 }
18 inline void addedge(int a,int b)
19 {
20     e[cnt]={b,head[a]};
21     head[a]=cnt++;
22 }
23 void tarjan(int u)
24 {
25     dfn[u]=low[u]=++idx;vis[u]=1;
26     st.push(u);
27     for(int i=head[u];i!=-1;i=e[i].next)
28     {
29         if(!dfn[e[i].to]) tarjan(e[i].to),low[u]=min(low[u],low[e[i].to]);
30         else if(vis[e[i].to]) low[u]=min(low[u],dfn[e[i].to]);
31     }
32     if(low[u]==dfn[u])
33     {
34         scnt++;
35         int v=-1;
36         while(v!=u)
37         {
38             v=st.top();st.pop();
39             col[v]=scnt,vis[v]=0;
40         }
41     }
42 }
43 int main()
44 {
45     while(~scanf("%d",&n))
46     {
47         scanf("%d",&m);
48         init();
49         while(m--)
50         {
51             scanf("%d%d%d%d",&a,&b,&fla,&flb);
52             addedge((a<<1)+fla,((b<<1)+flb)^1);
53             addedge((b<<1)+flb,((a<<1)+fla)^1);
54         }
55         for(int i=0;i<2*n;i++)
56             if(!dfn[i]) tarjan(i);
57         for(int i=0;i<2*n;i+=2)
58             if(col[i]==col[i^1]){puts("NO");flag=1;break;}
59         if(!flag) puts("YES");
60     }
61 }