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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=405,M=2005;
typedef long long ll;
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;
}
inline void get(int &x,char &c){
    c=getchar();
    while(c!=‘h‘&&c!=‘m‘) c=getchar();
    x=read()<<1;
}
int n,m,x,y;
char cx,cy;
struct edge{
    int v,ne;
}e[M];
int h[N],cnt=0;
inline void ins(int u,int v){
    cnt++;
    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
int dfn[N],low[N],dfc,belong[N],scc;
int st[N],top;
void dfs(int u){
    dfn[u]=low[u]=++dfc;
    st[++top]=u;
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }else if(!belong[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc++;int x=0;
        while(x!=u){
            x=st[top--];
            belong[x]=scc;
        }
    }
}
bool judge(){
    for(int i=1;i<=n;i++) if(belong[(i<<1)-1]==belong[i<<1]) return false;
    return true;
}
int main(){
    freopen("in","r",stdin);
    int T=read();
    while(T--){
        cnt=0;memset(h,0,sizeof(h));
        n=read();m=read();
        for(int i=1;i<=m;i++){
            get(x,cx);get(y,cy);//m 2i-1 ; h 2i
            if(cx==‘m‘){
                if(cy==‘m‘) ins(x,y-1),ins(y,x-1);
                if(cy==‘h‘) ins(x,y),ins(y-1,x-1);
            }
            if(cx==‘h‘){
                if(cy==‘m‘) ins(x-1,y-1),ins(y,x);
                if(cy==‘h‘) ins(x-1,y),ins(y-1,x);
            }
        }
        int _=n<<1;
        for(int i=1;i<=_;i++) dfn[i]=low[i]=belong[i]=0;
        for(int i=1;i<=_;i++) if(!dfn[i]) dfs(i);
        if(judge()) puts("GOOD");
        else puts("BAD");
    }
}