HDU 3062

2-SAT问题

有必要写一下<i,j>边的含义。所谓，选i必选j的意思是，因为每一对中只能有一个被选，则矛盾的对中若其中一被选i，另一个不可能是j'，因为存在矛盾，所以必选 j.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int MAXN=2100;
 9 const int MAXM=1000000;
10 
11 int head[MAXN],stack[MAXN],dfn[MAXN],low[MAXN];
12 int belong[MAXN],pat;
13 int st[MAXN],stop;
14 
15 struct {
16     int u,v;
17     int next;
18 }edge[MAXM];
19 int n,m,tot,index;
20 
21 void init(){
22     memset(head,-1,sizeof(head));
23     for(int i=0;i<=2*n;i++){
24         dfn[i]=low[i]=0;
25         belong[i]=-1;
26         stack[i]=0;
27     }
28 }
29 
30 void addedge(int u,int v){
31     edge[tot].u=u;
32     edge[tot].v=v;
33     edge[tot].next=head[u];
34     head[u]=tot++;
35 }
36 
37 void tarjan(int u){
38     int v;
39     dfn[u]=low[u]=++index;
40     st[stop++]=u; stack[u]=1;
41     for(int e=head[u];e!=-1;e=edge[e].next){
42         v=edge[e].v;
43         if(dfn[v]==0){
44             tarjan(v);
45             low[u]=min(low[u],low[v]);
46         }
47         else if(stack[v]==1){
48             low[u]=min(low[u],dfn[v]);
49         }
50     }
51     if(dfn[u]==low[u]){
52         pat++;
53         do{
54             v=st[--stop];
55             stack[v]=0;
56             belong[v]=pat;
57         }while(u!=v);
58     }
59 }
60 
61 int main(){
62     int a1,a2,b1,b2;
63     while(scanf("%d",&n)!=EOF){
64         init();
65         tot=0; index=0;
66         pat=-1; stop=0;
67         scanf("%d",&m);
68         for(int i=1;i<=m;i++){
69             scanf("%d%d%d%d",&a1,&a2,&b1,&b2);
70             addedge(2*a1+b1,((2*a2+b2)^1));
71             addedge(2*a2+b2,((2*a1+b1)^1));
72         }
73         for(int i=0;i<2*n;i++){
74             if(dfn[i]==0)
75             tarjan(i);
76         }
77         bool flag=false;
78         for(int i=0;i<n;i++){
79             if(belong[2*i]==belong[2*i+1]){
80                 printf("NO
");
81                 flag=true;
82                 break;
83             }
84         }
85         if(!flag){
86             printf("YES
");
87         }
88     }
89     return 0;
90 }

View Code