hdu 4115 石頭剪子布（2-sat問題）
/*
題意：石頭剪子布，現在已知n回合bob將會出什麼，對alice有限制，對於u,v,w；如果w=0說明a,b回合必須出的一樣
否則，必須不一樣。alice如果輸一回合就輸了，否則就贏了
解：
2-sat
alice有兩個選擇要麼平手要麼贏。
對於第u回合，alice可以出au，bu；
對於第v回合，alice可以出av，bv；
當w=0那麼第u回合和第v回合必須相同
比較au和bu。bv是否矛盾，如果矛盾建兩條邊
比較av和bu。bv是否矛盾，如果矛盾建兩條邊
當w=1第u回合和第v回合必須不相同
比較au和bu。bv是否矛盾，如果矛盾建兩條邊
比較av和bu。bv是否矛盾，如果矛盾建兩條邊
*/
#include
#include
#include
#include
using namespace std;
#define N 21000
#define NN 11000
struct node
{
int u,v,next;
} bian[NN*20];
int head[N],yong,low[N],dfn[N],belong[N],ans,top,index,stac[N],vis[N];
void init()
{
memset(head,-1,sizeof(head));
yong=index=ans=top=0;
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
}
void addedge(int u,int v)
{
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
void tarjan(int u)
{
low[u]=dfn[u]=++index;
stac[++top]=u;
vis[u]=1;
int i;
for(i=head[u]; i!=-1; i=bian[i].next)
{
int v=bian[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
ans++;
int t;
do
{
t=stac[top--];
belong[t]=ans;
vis[t]=0;
}
while(t!=u);
}
}
int slove(int n)
{
int i;
for(i=0; i
