显然的 $2-sat$ 问题，甚至不用输出方案
每种菜不是汉式就是满式，分成两个节点 $i,n+i$ 分别表示满式和汉式
对于限制 $m_i,m_j$，如果 $i$ 为汉式则 $j$ 一定要为满式，如果 $j$ 为汉式 $i$ 一定为满式
所以连边 $(n+i,j),(n+j,i)$
其他情况同理，最后 $Tarjan$ 缩一下联通块看看是否某一个联通块同时包含 $i,n+i$ 即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; int T,n,m; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } int dfn[N],low[N],bel[N],dfs_clock,cnt; int st[N],Top; inline void clr() { dfs_clock=0,cnt=0,Top=0,cntt=0; for(int i=1;i<=n*2;i++) fir[i]=dfn[i]=low[i]=bel[i]=0; } void Tarjan(int x) { dfn[x]=low[x]=++dfs_clock; st[++Top]=x; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(!dfn[v]) Tarjan(v),low[x]=min(low[x],low[v]); else if(!bel[v]) low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { cnt++; while(st[Top]!=x) bel[st[Top--]]=cnt; bel[st[Top--]]=cnt; } } int main() { T=read(); char s1[7],s2[7]; while(T--) { clr(); n=read(),m=read(); for(int i=1;i<=m;i++) { scanf("%s%s",s1,s2); int u=0,v=0; for(int k=1;s1[k]>='0'&&s1[k]<='9';k++) u=u*10+s1[k]-'0'; for(int k=1;s2[k]>='0'&&s2[k]<='9';k++) v=v*10+s2[k]-'0'; if(s1[0]=='m') { if(s2[0]=='m') add(n+u,v),add(n+v,u); else add(n+u,n+v),add(v,u); } else { if(s2[0]=='m') add(u,v),add(n+v,n+u); else add(u,n+v),add(v,n+u); } } bool GG=0; for(int i=1;i<=n*2;i++) if(!dfn[i]) Tarjan(i); for(int i=1;i<=n;i++) if(bel[i]==bel[n+i]) GG=1; if(GG) printf("BAD "); else printf("GOOD "); } return 0; }