Aimee

2-sat的模板题

显然根据题目所给内容，我们可以根据每一个菜的做法，推断出另一个菜的做法，然后连边

这样会出现一个个的环，这个环不能有矛盾

也就是满式和汉式不能同时被推出

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define int long long 
using namespace std;
int low[500005];
int dfn[500005];
int be[500005];
int sp,p;
int ti;
int head[5000005];
struct e{
    int to;
    int ne;
}ed[5000005];
string s1,s2;
int k;
int n,m;
stack<int> s;
void add(int f,int to){
    p++;
    ed[p].ne=head[f];
    head[f]=p;
    ed[p].to=to;
    return ;
}
void tarjan(int r){
    low[r]=dfn[r]=++ti;
    s.push(r);
    for(int i=head[r];i;i=ed[i].ne){
        int v=ed[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[r]=min(low[r],low[v]);
        }else{
            if(!be[v]){
                low[r]=min(low[r],dfn[v]);
            }
        }
    }
    if(low[r]==dfn[r]){
        sp++;
        while(s.top()!=r){
            int x=s.top();
            s.pop();
            be[x]=sp;
        }
        s.pop();
        be[r]=sp;
    }
}
void ini(){
    p=0;
    sp=0;
    ti=0;
    memset(head,0,sizeof(head));
    memset(be,0,sizeof(be));
    memset(dfn,0,sizeof(dfn));

}
signed main(){
    scanf("%d",&k);
    while(k--){
        ini();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            cin>>s1>>s2;
            int x=0;
            int y=0;
            for(int i=1;i<s1.length();++i){
                x=x*10+s1[i]-'0';
            }
            for(int i=1;i<s2.length();++i){
                y=y*10+s2[i]-'0';
            }
            if(s1[0]=='m'){
                if(s2[0]=='m'){
                    add(x+n,y);
                    add(y+n,x);
                }else{
                    add(x+n,y+n);
                    add(y,x);
                }
            }
            if(s1[0]=='h'){
                if(s2[0]=='h'){
                    add(x,y+n);
                    add(y,x+n);
                }else{
                    add(x,y);
                    add(y+n,x+n);
                }
            }
        }
        for(int i=1;i<=n;++i)
            if(!dfn[i])
                tarjan(i);
        int f=1;
        for(int i=1;i<=n;++i){
            if(be[i]==be[i+n]){
                f=0;
                break;
            }
        }
        if(f==0){
            printf("BADn");
        }else{
            printf("GOODn");
        }
    }
    return 0;
}