[文章目录]
Description
有n种材料，m个评审员，每个评审员有两个要求，至少满足其中一个即可通过评审。要求类似第x道菜需要通过满/汉式做出来。询问能否有一种方案来做n种材料，使得通过全部评审员。多组数据<=50 n<=100 m<=1000
2-sat。
对于每个材料建两个点表示两种选择，对于一个限定a1或b2，我们连边a2->b2 b1->a1，表示如果a选择了1，那么b必须选择2，如果b选择了1，a必须选择1。建造的图中没有任何两点x1,x2相互可达即有解。
两种算法：
1.对于每对点中的一个进行搜索，标记种类，如果不合法，更换为另一个。如果都不合法即无解。时间复杂度O(nm)
2.tarjan原图，枚举点对，都不在一个强连通分量中即有解。复杂度O(m)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
char ch=getchar();
while(ch!=EOF&&ch!='m'&&ch!='h') ch=getchar();
return ch=='h';
}
int n,m;
int head[300],to[2100],nxt[2100],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int dfn[300],low[300],tim,z[300],top,bel[300],bs;
bool inz[300];
void tarjan(int x)
{
low[x]=dfn[x]=++tim; z[++top]=x; inz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
else if(inz[to[i]]) low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
int t; bs++;
do
{
t=z[top--];
inz[t]=0;
bel[t]=bs;
}while(t!=x);
}
}
int main()
{
int t; scanf("%d",&t);
while(t--)
{
memset(head,0,sizeof head); cnt=0;
memset(dfn,0,sizeof dfn); tim=bs=0;
scanf("%d%d",&n,&m);
int fl1,fl2,a,b;
while(m--)
{
fl1=read(); scanf("%d",&a);
fl2=read(); scanf("%d",&b);
add((a<<1)|(fl1^1),(b<<1)|fl2);
add((b<<1)|(fl2^1),(a<<1)|fl1);
}
for(int i=2;i<=2*n+1;++i) if(!dfn[i]) tarjan(i);
fl1=1;
for(int i=1;i<=n;++i) if(bel[i<<1]==bel[i<<1|1]) fl1=0;
if(fl1) puts("GOOD");
else puts("BAD");
}
return 0;
}