题意：给你一张2-SAT，问你加至少几句a V b（不能用非运算）这样的语句，使得其无法全为真。
如果最开始没有左右两项都含非运算的析取表达式，则无解，因为显然你可以对每一项的不含非的那项规定为真，使得整个2-SAT成立。
由于规定了你添加的语句不能含有非运算，故添加的边一定从 非某 指向 某。
如果一开始就存在某个a，它和非a互相可达，则答案为0。
如果一开始某个非a能到达a，则答案为1；如果一开始存在某个非j，a能到达非j，并且存在某个i，i能到达非a，则答案也为1，显然可以添一条从非某指向某的边使得a和非a互相可达。
其余情况输出2。
#includeusing namespace std;int n,m,x[2005],y[2005];bool can[2005*2][2005*2];int first[2005*2],v[4005],nex[4005],e;void AddEdge(int U,int V){ v[++e]=V; nex[e]=first[U]; first[U]=e;}void dfs(int from,int U){ can[from][U]=1; for(int i=first[U];i;i=nex[i]){ if(!can[from][v[i]]){ dfs(from,v[i]); } }}int main(){ //freopen("k.in","r",stdin); bool flag=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ scanf("%d%d",&x[i],&y[i]); if(x[i]<0 && y[i]<0){ flag=1; } } if(!flag){ puts("-1"); return 0; } for(int i=1;i<=m;++i){ if(x[i]>0 && y[i]>0){ AddEdge(x[i]+n,y[i]); AddEdge(y[i]+n,x[i]); } else if(x[i]>0 && y[i]<0){ AddEdge(x[i]+n,-y[i]+n); AddEdge(-y[i],x[i]); } else if(x[i]<0 && y[i]>0){ AddEdge(-x[i],y[i]); AddEdge(y[i]+n,-x[i]+n); } else{ AddEdge(-x[i],-y[i]+n); AddEdge(-y[i],-x[i]+n); } } for(int i=1;i<=n*2;++i){ dfs(i,i); } /*for(int i=1;i<=n*2;++i){ for(int j=1;j<=n*2;++j){ printf("%d ",can[i][j]); } puts(""); }*/ for(int i=1;i<=n;++i){ if(can[i][i+n] && can[i+n][i]){ puts("0"); return 0; } } for(int i=1;i<=n;++i){ if(can[i][i+n]){ puts("1"); return 0; } } for(int i=1;i<=n;++i){ if(can[n+i][i]){ bool f1=0; for(int j=1;j<=n;++j){ if(can[i][j+n]){ f1=1; break; } } if(f1){ bool f2=0; for(int j=1;j<=n;++j){ if(can[j][i+n]){ f2=1; break; } } if(f2){ puts("1"); return 0; } } } } /*for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j)if(j!=i){ if(can[j][i] && can[j][i+n] && can[i][j+n] && can[i+n][j+n]){ puts("1"); return 0; } } } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(can[i][j] && can[i][j+n]){ puts("1"); return 0; } } }*/ puts("2"); return 0;}