\(Descripion:\)

给出 \(n\) 种材料，有 \(m\) 个人，每个人会要求对某种材料进行汉式和满式两种加工。

一种材料只能用一次，问是否有可能满足全部人的要求。（满足定义是有一项他提出的菜做了）。

\(Sample\) \(Input:\)

2

3 4

m3 h1

m1 m2

h1 h3

h3 m2

2 4

h1 m2

m2 m1

h1 h2

m1 h2

\(Sample\) \(Output:\)

GOOD

BAD

\(Solution:\)

这种题有两种状态，只能在这两种状态里选，并且有限制，很明显是 \(2-SAT\) 的题。

考虑把满和汉两种烹饪分成两种状态，连边其实就是 或运算 连边

也就是如果这个点不选，那另一个肯定得选，如果另一个不选，那这个就就得选。

#include
    
     using namespace std;int n,m,k,En,num,cnt,top;const int N=205,M=2005;int scc[N+N],head[N+N],dfn[N+N],low[N+N];int s[N+N],ins[N+N];char s1[10],s2[10];struct edge {    int next,to;}E[M<<1];inline void Get(int &a,int &b){    char ch=getchar();    while(ch!='h' && ch!='m') ch=getchar();    a=(ch=='h');    scanf("%d",&b);}inline void add(int from,int to){    E[++En].next=head[from];    E[En].to=to;    head[from]=En;} inline void tarjan(int u){    dfn[u]=low[u]=++num;    ins[u]=1;    s[++top]=u;    for(int i=head[u];i;i=E[i].next){        int v=E[i].to;        if(!dfn[v]){            tarjan(v);            low[u]=min(low[u],low[v]);        }        else if(ins[v])            low[u]=min(low[u],dfn[v]);    }    if(dfn[u]==low[u]){        scc[u]=++cnt;        ins[u]=0;        while(s[top]!=u){            ins[s[top]]=0;            scc[s[top]]=cnt;            top--;        }        top--;    }}inline bool two_sat(){    for(int i=1;i<=n;++i)        if(scc[i]==scc[i+n]) return false;    return true;}int main(){    scanf("%d",&k);    while(k--){        num=cnt=En=0;        memset(scc,0,sizeof(scc));        memset(head,0,sizeof(head));        memset(dfn,0,sizeof(dfn));        memset(low,0,sizeof(low));        memset(E,0,sizeof(E));        memset(ins,0,sizeof(ins));        scanf("%d%d",&n,&m);        for(int i=1;i<=m;++i){            int ax=0,ay=0;            int bx=0,by=0;            Get(ax,ay);            Get(bx,by);            add(ay+(!ax)*n,by+n*bx);            add(by+(!bx)*n,ay+n*ax);        }        for(int i=1;i<=n+n;++i)            if(!dfn[i]) tarjan(i);        if(two_sat()) puts("GOOD");        else puts("BAD");    }    return 0;}