1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6 using namespace std;  7   8 const int MAXN=2010;  9 const int MAXM=2100100; 10  11 int head[MAXN],dfn[MAXN],low[MAXN],st[MAXN],stop,belong[MAXN],tot,index,pat; 12 bool stack[MAXN]; 13 struct { 14     int u,v; 15     int next; 16 }edge[MAXM]; 17 int n,m; 18 int s1,s2; 19  20 void init(){ 21     stop=0; tot=0; index=0; pat=-1; 22     for(int i=0;i<2*n;i++){ 23         head[i]=-1; 24         dfn[i]=low[i]=0; 25         belong[i]=-1; 26         stack[i]=false; 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]=true; 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]){ 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]=false; 56             belong[v]=pat; 57         }while(u!=v); 58     } 59 } 60  61 int main(){ 62     int u,v; 63     while(scanf("%d%d",&n,&m)!=EOF){ 64         init(); 65         for(int i=1;i<=m;i++){ 66             scanf("%d%d",&s1,&s2); 67             u=abs(s1)-1; 68             v=abs(s2)-1; 69         //    cout<<u<<‘ ‘<<v<<endl; 70             if(s1>0&&s2>0){ 71                 addedge(2*u,2*v+1); 72                 addedge(2*v,2*u+1); 73             } 74             else if(s1>0&&s2<0){ 75                 addedge(2*u,2*v); 76                 addedge(2*v+1,2*u+1); 77             } 78             else if(s1<0&&s2>0){ 79                 addedge(2*u+1,2*v+1); 80                 addedge(2*v,2*u); 81             } 82             else{ 83                 addedge(2*u+1,2*v); 84                 addedge(2*v+1,2*u); 85             } 86         } 87         for(int i=0;i<2*n;i++){ 88             if(dfn[i]==0) 89             tarjan(i); 90         } 91         bool flag=true; 92         for(int i=0;i<n;i++){ 93             if(belong[i*2]==belong[i*2+1]){ 94                 printf("0\n"); 95                 flag=false; 96                 break; 97             } 98         } 99         if(flag)100         printf("1\n");101     }102 }