标签：2-sat，tarjan缩点

题目

题目传送门

Description

满汉全席是中国最丰盛的宴客菜肴，有许多种?同的材?透过满族或是汉族的??方式，呈现在??繁多的菜色之中。由于菜色众多而繁杂，只有极少?博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。 世界满汉全席协会是由能够??满汉全席的专家厨师们所组成，而他们之间还细分为许多?同等级的厨师。为?招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在?赛的厨师之中，找到满汉??界的明日之星。 大会的规则如下：每位?赛的选手可以得到n 种材?，选手可以自由选择用满式或是汉式??将材?当成菜肴。大会的评审制?是：共有m 位评审员分别把关。每一位评审员对于满汉全席有各自独特的?解，但基本见解是，要有?样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就?能算是满汉全席。但避免过于有主?的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出?的?况下，才能淘汰一位选手，否则?能淘汰一位?赛者。换?话?，只要?赛者能在这?种材?的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材?有猪肉，羊肉和牛肉时，有四位评审员的喜好如下表： 评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉 如?赛者甲做出满式猪肉，满式羊肉和满式牛肉??，他将无法满足评审三的要求，无法通过评审。而?赛者乙做出汉式猪肉，满式羊肉和满式牛肉??，就可以满足所有评审的要求。 但大会后?发现，在这样的制?下如果材?选择跟派出的评审员没有特别安排好的话，所有的?赛者最多只能通过部分评审员的审查而?是全部，所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时，则???赛者采取?么样的做法，都?可能通过所有评审的考核： 评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉 所以大会希望有人能写一个程序?判断，所选出的m 位评审，会?会发生 没有人能通过考核的窘境，以?协会组织合适的评审团。
Input

第一?包含一个数字 K，代表测试文件包含?K 组资?。每一组测试资?的第一?包含?个数字n 跟m（n≤100，m≤1000），代表有n 种材?，m 位评审员。为方?起?，材?舍弃中文名称而给予编号，编号分别从1 到n。接下?的m ?，每?都代表对应的评审员所拥有的?个喜好，每个喜好由一个英文字母跟一个数字代表，如m1 代表这个评审喜欢第1 个材?透过满式??做出?的菜，而h2 代表这个评审员喜欢第2 个材?透过汉式??做出?的菜。每个测试文件?会有超过50 组测试资?
Output

每笔测试资?输出一?，如果?会发生没有人能通过考核的窘境，输出GOOD；否则输出BAD（大写字母）。
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

HINT

Source

JSOI2010第二轮Contest2

分析

裸的2-sat问题

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int maxn=1e6+6;
int Que,n,m,cnt=1,ind,scc,top,last[maxn],dfn[maxn],low[maxn],que[maxn],belong[maxn];
bool inq[maxn];
struct edge{
   int to,next;}e[maxn<<2];
int get()
{int x;char ch=getchar();while(ch!='m'&&ch!='h')ch=getchar();if(ch=='m')x=read()*2;else x=read()*2-1;return x;
}void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void tarjan(int x){low[x]=dfn[x]=++ind;inq[x]=1;que[++top]=x;reg(x)if(!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);if(low[x]==dfn[x]){int now=0;scc++;while(now!=x){now=que[top--];belong[now]=scc;inq[now]=0;}}
}
int main()
{Que=read();while(Que--){top=ind=cnt=scc=0;n=read(),m=read();rep(i,1,n*2)last[i]=dfn[i]=0;rep(i,1,m){int x=get(),y=get(),xp,yp;if(x%2==0)xp=x--;else xp=x++;if(y%2==0)yp=y--;else yp=y++;insert(xp,y);insert(yp,x);}bool flag=0;rep(i,1,2*n)if(!dfn[i])tarjan(i);rep(i,1,n)if(belong[2*i]==belong[2*i-1]){puts("BAD");flag=1;break;}if(!flag)puts("GOOD");}return 0;
}