题解 | #[JSOI2010]满汉全席#

2-sat问题： 解读题意后可知： 满足裁判的喜好之一：转换成数学思维则是: A or B = True ; 但是容易漏掉的一点是：每种食材只能被做成一种类型的食物 ； 故需进行预处理： 食材做法 ： A1 ！= A2 ； 做法一和二相隔2n ； 下面是代码：

//ios::sync_with_stdio(false); 加快 cin和cout的运行效率.
//cin.tie(0),cout.tie(0);  进一步加快执行效率.    不能和scanf与printf连用.
//cout << fixed << setprecision() << ;
//floor();向下取整
//ceil();向上取整
//rand();随机数
#include <bits/stdc++.h>
using namespace std;
//typedef long long ll; //  -9223372036854775807ll - 1 ~ 9223372036854775807ll 9e+18
//typedef unsigned long long ull;
//typedef unsigned int uint;
#define int long long
#define INF 0X7FFFFFFF
#define MAXN 1000005
#define nullptr 0
#define debug(x) cout<<#x<<" : "<<x<<endl
#define Enter(i,n) (i==n) ? cout<<endl : cout<<" "
#define loop(i,x,n) for( int i = x ; i <= n ; ++i )
#define loop_(i,x,n) for( int i = x ; i >= n ; --i )
#define input(x) scanf("%lld",&x)
#define output(x) printf("%lld",x)
#define new_line printf("\n")
#define blank printf(" ")
const int MAX=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int Max=998244353;
const double eps=1e-8;
void init();
void solve();
int GCD(int a,int b);
inline int read();
inline void write(int x);
int min(int x,int y){if(x<=y)return x;return y;}
int max(int x,int y){if(x>=y)return x;return y;}
//int Go[4][2]={ {1,0},{0,1},{-1,0},{0,-1} };

int QuickPow( int x , int pow )
{
    int res = 1 ;
//    x %= Max ;
//    pow %= Max ;
    while( pow ){
        if( pow & 1 ) res = ( res * x ) ;
        x = ( x * x ) ;
        pow >>= 1 ;
    }
    return res ;
}

bool Is_prime(int x)
{
    if( x == 0 || x == 1 ) return false ;
    if( x == 2) return true ;
    for( int i = 2 ; i*i <= x ; i++ ){
        if( x%i == 0 ) return false ;
    }
    return true ;
}

#define often 1e6 + 5 
// ------------------------------------------------------------

vector< int > G[MAXN] ;
vector< int > RG[MAXN] ;
vector< int > v ;
bool vis[MAXN] ;
int sccon[MAXN] ;
void dfs1( int x )
{
    vis[x] = 1 ;
    loop( i , 0 , (int)G[x].size()-1 ){
        if( !vis[ G[x][i] ] ) dfs1( G[x][i] ) ;
    }
    v.push_back( x ) ;
    return ;
}
void dfs2( int x , int num )
{
    vis[x] = 0 ;
    sccon[x] = num ;
    loop( i , 0 , (int)RG[x].size()-1 ){
        if( vis[ RG[x][i] ] ) dfs2( RG[x][i] , num ) ;
    }
    return ;
}
int scc( int n )
{
    v.clear() ;
    memset( vis , 0 , sizeof vis ) ;
    memset( sccon , 0 , sizeof sccon ) ;
    int cnt = 0 ;
    loop( i , 1 , n ){
        if( !vis[ i ] ) dfs1( i ) ;
    }
    loop_( i , (int)v.size()-1 , 0 ){
        if( vis[ v[i] ] ) dfs2(  v[i] , cnt++ ) ;
    }
    return cnt ;
}
void solve()
{
    int n , m ;
    cin >> n >> m ;
    loop( i , 1 , 4*n ){
        G[i].clear();
        RG[i].clear() ;
    }
    char c ;
    char h ;
    int a ;
    int b ;
    loop( i , 1 , n ){
        G[ i ].push_back( i+n+2*n ) ;
        G[ i+n+2*n ].push_back( i ) ;
        G[ i+n ].push_back( i+2*n ) ;
        G[ i+2*n ].push_back( i+n ) ;

        RG[ i ].push_back( i+n+2*n ) ;
        RG[ i+n+2*n ].push_back( i ) ;
        RG[ i+n ].push_back( i+2*n ) ;
        RG[ i+2*n ].push_back( i+n ) ;
    }
    loop( i , 1 , m ){
        cin >> c >> a ;
        cin >> h >> b ;
        if( c == 'h' ) a += n ;
        if( h == 'h' ) b += n ;
        G[ a+2*n ].push_back( b ) ;
        G[ b+2*n ].push_back( a ) ;
        RG[ b ].push_back( a+2*n ) ;
        RG[ a ].push_back( b+2*n ) ;
    }
    int cnt = scc( 4*n ) ;
    bool flag = 0 ;
    loop( i , 1 , 2*n ){
        // cout << i << " " << sccon[i] << endl ;
        if( sccon[i] == sccon[i+2*n] ){
            flag = 1 ;
            break ;
        }
    }
    if( !flag ) puts("GOOD");
    else puts("BAD") ;
    return ; 
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
//    clock_t start,last;
//    start = clock();
    init() ;
    int _ = 1 ;
    // input( _ ) ;
    cin >> _ ;
    while( _-- ){
//        srand( (int)time(0) ) ;
        solve() ;
    }
//    system("pause");
//    last = clock();
//    cout<<(double)(last-start)/CLOCKS_PER_SEC;
//    printf("%lf\n",(double)(last-start)/CLOCKS_PER_SEC ) ;
    return 0;
}

void init()
{
    return ;
}

int GCD(int a,int b)
{
    if(b)return GCD(b,a%b);
    return a;
}

// inline int read()
// {
//    register int x = 0, t = 1;
//    register char ch=getchar(); // 读入单个字符到寄存器
//    while(ch<'0'||ch>'9'){
//        if(ch=='-')t=-1;
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);  // 移位与异或
//      	// 第十行可以换成 x = x * 10 + ch - '0'
//        ch=getchar();
//    }
//    return x*t;
// }

// inline void write(int x)
// {
//    if(x<0){
//    	putchar('-');
// 		x=-x;
// 	}
//    if(x>9) write(x/10);
//    putchar(x%10+'0');
// }