题目链接：
?id=3905
题目大意：
有N个候选人，，有M组要求，每组要求关系到候选中的两个人A和B，"+A +B"表示A和B中至少
有一人被选中，"-A -B"表示A和B中至少有一人不被选中。"+A -B"表示A被选中和B不被选中两
件事至少发生一件。"-A +B"表示A不被选中和B被选中至少发生一件。那么问题来了：是否存在
M组要求全部符合的方案。
思路：在本题中，每个人都有两种状态，一种是选中，一种是不选中。可以把一个人i拆成两个点
Pi和P(i+N)，分别表示当选和落选。那么两个人i和j的关系就可以表示为以下四种：
i和j至少有一个人当选：i->j+N，j->i+N
i和j至少有一个人落选：i+N->j，j+N->i
i当选，j落选： i->j，j+N->i+N
i落选，j当选： i+N->j+N，j->i
那么根据上面的关系建有向图，那么问题就变为从图中选出N个点，并且Ai和A(i+N)的点不能同时
被选择，使其满足2-SAT条件。求出图的强连通分量，如果选中强连通分量中的一个点，那么就必
须选中强连通分量中的所有点，如果Ai和!Ai都在一个强连通分量里，则产生矛盾，那么2-SAT无解。
如果都不在一个强连通分量里，则2-SAT有解。最后的步骤就是用Tarjan了求强连通分量并缩点，之
后判断是否存在Ai和A(i+N)在一个强连通分量里。如果存在，则方案不满足，如果不存在，则方案
满足。
AC代码：
<span style="font-family:Microsoft YaHei;font-size:18px;">#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<queue>using namespace std;const int MAXN = 2200;const int MAXM = MAXN*MAXN;struct EdgeNode{int to;int next;}Edges[MAXM];int Head[MAXN];int dfn[MAXN],low[MAXN],belong[MAXN],Stack[MAXN],vis[MAXN];int m,id,lay,scc,N,M;void AddEdges(int u,int v){Edges[id].to = v;Edges[id].next = Head[u];Head[u] = id++;}void TarBFS(int pos){dfn[pos] = low[pos] = ++lay;Stack[m++] = pos;vis[pos] = 1;for(int i = Head[pos]; i != -1; i = Edges[i].next){int v = Edges[i].to;if( !dfn[v] ){TarBFS(v);low[pos] = min(low[pos],low[v]);}else if(vis[v])low[pos] = min(low[pos],low[v]);}int v;if(dfn[pos] == low[pos]){++scc;do{v = Stack[–m];belong[v] = scc;vis[v] = 0;}while(v != pos);}}int main(){int u,v;while(~scanf("%d%d",&N,&M)){id = m = scc = lay = 0;memset(Head,-1,sizeof(Head));memset(vis,0,sizeof(vis));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(belong,0,sizeof(belong));for(int i = 0; i < M; ++i){scanf("%d%d",&u,&v);int a = abs(u);int b = abs(v);if(u > 0 && v > 0){AddEdges(a+N,b);AddEdges(b+N,a);}if(u < 0 && v < 0){AddEdges(a,b+N);AddEdges(b,a+N);}if(u > 0 && v < 0){AddEdges(a+N,b+N);AddEdges(b,a);}if(u < 0 && v > 0){AddEdges(a,b);AddEdges(b+N,a+N);}}for(int i = 1; i <= 2*N; ++i)if( !dfn[i] )TarBFS(i);int ans = 1;for(int i = 1; i <= N; ++i){if(belong[i] == belong[i+N]){ans = 0;break;}}printf("%d\n",ans);}return 0;}</span>
便是不再存在着任何我曾经对你有过的希望。
