hdu3062 Party（2-sat）

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int N=2e3+5;
 8 int low[N],dfn[N],Stack[N],belong[N];
 9 bool inStack[N];
10 int n,m,tot,tag,top;
11 vector<int> G[N];
12 
13 void init(){
14     top=tag=0;
15     memset(low,0,sizeof low);
16     memset(dfn,0,sizeof dfn);
17     memset(Stack,0,sizeof Stack);
18     memset(belong,0,sizeof belong);
19     memset(inStack,false,sizeof inStack);
20     for(int i=0;i<N;i++){
21         G[i].clear();
22     }
23 }
24 
25 void tarjan(int u){
26     int v;
27     low[u]=dfn[u]=++tot;
28     Stack[++top]=u;
29     inStack[u]=true;
30     for(int i=0;i<G[u].size();i++){
31         v=G[u][i];
32         if(dfn[v]==0){
33             tarjan(v);
34             low[u]=min(low[u],low[v]);
35         }
36         else if(inStack[v]==true){
37             low[u]=min(low[u],dfn[v]);
38         }
39     }
40     if(dfn[u]==low[u]){
41         tag++;
42         do{
43             v=Stack[top--];
44             inStack[v]=false;
45             belong[v]=tag;
46         }while(u!=v);
47     }
48 }
49 
50 int main(){
51     int a1,a2,c1,c2;
52     while(~scanf("%d",&n)){
53         scanf("%d",&m);
54         init();
55         for(int i=0;i<m;i++){
56             scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
57             G[a1*2+c1].push_back(a2*2+(1-c2));
58             G[a2*2+c2].push_back(a1*2+(1-c1));
59         }
60         for(int i=0;i<2*n;i++){
61             if(dfn[i]==0){
62                 tot=0;
63                 tarjan(i);
64             }
65         }
66         int flag=1;
67         for(int i=0;i<n;i++){
68             if(belong[i*2]==belong[i*2+1]){
69                 flag=0;
70                 break;
71             }
72         }
73         if(flag==1)printf("YES\n");
74         else printf("NO\n");
75     }
76 }