# BZOJ 1823: [JSOI2010]满汉全席(2-SAT)

2018-03-01 12:22:20来源:cnblogs.com作者:自为风月马前卒人点击

2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2

## Sample Output

GOOD
好久没自己做出过题了QWQ....2-SAT的裸题。。对于(A,B)必须选一个的这种我们可以认为选\$A'\$必选\$B\$，选\$B'\$必选\$A\$然后来一遍tarjan就好啦
`#include<cstdio>#include<cstring>#include<algorithm>#include<stack>#include<vector>#include<queue>#include<iostream>#define Pair pair<int,int>#define F first#define S secondusing namespace std;const int MAXN=1e6+10;//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)char buf[1<<20],*p1=buf,*p2=buf;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct node{    int u,v,nxt;}edge[MAXN];int head[MAXN],num=1;int dfn[MAXN],low[MAXN],tot=0,color[MAXN],vis[MAXN],colornum=0;stack<int>s;inline void AddEdge(int x,int y){    edge[num].u=x;    edge[num].v=y;    edge[num].nxt=head[x];    head[x]=num++;}void tarjan(int now){    dfn[now]=low[now]=++tot;    s.push(now);    vis[now]=1;    for(int i=head[now];i!=-1;i=edge[i].nxt)    {        if(!dfn[edge[i].v])    tarjan(edge[i].v),low[now]=min(low[now],low[edge[i].v]);        else if(vis[edge[i].v]) low[now]=min(low[now],dfn[edge[i].v]);    }    if(dfn[now]==low[now])    {        int h;colornum++;        do        {            h=s.top();s.pop();            vis[h]=0;            color[h]=colornum;        }while(h!=now);    }}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif        int QWQ=read();    while(QWQ--)    {        int N=read(),M=read();        memset(dfn,0,sizeof(dfn));        memset(low,0,sizeof(low));        memset(head,-1,sizeof(head));        memset(vis,0,sizeof(vis));        memset(color,0,sizeof(color));        num=1;        int a,b;char x,y,temp;        for(int i=1;i<=M;i++)        {            while(x!='m'&&x!='h') x=getchar();            a=read();            while(y!='m'&&y!='h') y=getchar();            b=read();            if(x=='m')                 if(y=='h') AddEdge(a+N,b+N),AddEdge(b,a);                else AddEdge(a+N,b),AddEdge(b+N,a);            else                 if(y=='h') AddEdge(a,b+N),AddEdge(b,a+N);                else AddEdge(a,b),AddEdge(b+N,a+N);            x='0';y='0';        }        for(int i=1;i<=2*N;i++)            if(!dfn[i]) tarjan(i);        bool flag=1;        for(int i=1;i<=N;i++)            if(color[i]==color[i+N])                {printf("BAD/n");flag=0;break;}        if(flag==1) printf("GOOD/n");    }    return 0;}`