Luogu

BZOJ

分析

很裸的 $\mathrm{2-SAT}$ 。

把 $i$ 拆成 $i$ 和 $i+n$ ，分别表示汉式和满式。

对于每个要求 $(a_c,b_d)$ ，这样子连边：

• 如果 $a$ 为 $m$ ， $b$ 为 $m$ ，那么 $c$ 向 $d+n$ 连边，$d$ 向 $c+n$ 连边。
• 如果 $a$ 为 $m$ ， $b$ 为 $h$ ，那么 $c$ 向 $d$ 连边， $d+n$ 向 $c+n$ 连边。
• 如果 $a$ 为 $h$ ， $b$ 为 $m$ ，那么 $c+n$ 向 $d+n$ 连边， $d$ 向 $c$ 连边。
• 如果 $a$ 为 $h$ ， $b$ 为 $h$ ，那么 $c+n$ 向 $d$ 连边， $d+n$ 向 $c$ 连边。

$x$ 向 $y$ 连边的意义是如果满足 $x$ ，那么必须满足 $y$ 。

连完边后直接 $\mathrm{tarjan}$ 缩点，如果 $i$ 和 $i+n$ 在同一个强连通分量中就不合法。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200+10;
const int M=2000+10;

struct Edge { int v,nxt; } e[M];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int dfn[N],low[N],tim=0;
int bl[N],tot=0;
int sta[N],in[N],top=0;

inline void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        ++tot;
        while (233) {
            int now=sta[top--];
            bl[now]=tot,in[now]=0;
            if (u==now) break;
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),cnt=0;
        memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),tim=0;
        memset(bl,0,sizeof(bl)),tot=0;

        int n=read(),m=read();
        for (re int i=1;i<=m;++i) {
            char a=getchar(); int c=read();
            char b=getchar(); int d=read();
            if (a=='m'&&b=='m') addEdge(c,d+n),addEdge(d,c+n);
            if (a=='m'&&b=='h') addEdge(c,d),addEdge(d+n,c+n);
            if (a=='h'&&b=='m') addEdge(c+n,d+n),addEdge(d,c);
            if (a=='h'&&b=='h') addEdge(c+n,d),addEdge(d+n,c);
        }

        for (re int i=1;i<=n+n;++i)
            if (!dfn[i]) tarjan(i);

        int flag=1;
        for (re int i=1;i<=n;++i)
            if (bl[i]==bl[i+n]) { flag=0; break; }
        puts(flag?"GOOD":"BAD");
    }
    return 0;
}