51nod2861 2-sat

列如 h1 m2则 转换成 选了m1 必须选 m2即可

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 2010,M = 2010;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;

char a,b;
int head[N],to[M],last[M],cnt = 1;
void add(int a,int b){
    
    to[++cnt] = b;
    last[cnt] = head[a];
    head[a] = cnt;
}

int n,m;
int dfn[N],low[N],sta[N],top,scc_cnt,times;
int flag[N],id[N];
void tarjan(int x){
    
    dfn[x] = low[x] = ++times;
    sta[++top] = x,flag[x] = 1;
    for(int i = head[x]; i != -1; i = last[i]){
    
        int j = to[i];
        if(!dfn[j]){
    
            tarjan(j);
            low[x] = min(low[x],low[j]);
        }else if(flag[j]){
    
            low[x] = min(low[x],dfn[j]);
        }
    }

    if(dfn[x] == low[x]){
    
        ++scc_cnt;
        int y;
        do{
    
            y = sta[top--];
            id[y] = scc_cnt;
            flag[y] = 0;
        }while(y != x);
    }
}


int main(){
    
    int t;
    cin >>t;
    while(t--){
    
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof head);
        for(int i = 2; i <= n * 2 + 2; i++){
    
            id[i] = 0;
            dfn[i] = 0,low[i] = 0;
        }
        times = 0;
        scc_cnt = 0;
        cnt = 1;
        for(int i = 1; i <= m; i++){
    
            int c,d;
            getchar();
            scanf("%c%d %c%d",&a,&c,&b,&d);
            if(a == 'm' && b == 'm'){
    
                add(c * 2,d * 2 + 1);
                add(d * 2,c * 2 + 1);
            }else if(a == 'h' && b== 'm'){
    
                add(c * 2 + 1,d * 2 + 1);
                add(d * 2,c * 2);
            }else if(a == 'm' && b == 'h'){
    
                add(c * 2,d * 2);
                add(d * 2 + 1,c * 2 + 1);
            }else{
    
                add(c * 2 + 1,d * 2);
                add(d * 2 + 1,c * 2);
            }
        }

        for(int i = 2; i <= n * 2 + 1; i++){
    
            if(!dfn[i]) tarjan(i);
        }

        bool flag = true;
        for(int i = 1; i <= n; i++){
    
            if(id[i * 2] == id[i * 2 + 1]){
    
                flag = false;
                puts("BAD");
                break;
            }
        }


        if(flag) puts("GOOD");

    }

    return 0;
}