分析
很裸的 $\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;
}