QAQ注意读入 它有可能是两位甚至三位
然后其它就和普通2-SAT一样辣
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; #define Min(x,y) ((x)<(y)?(x):(y)) const int N=1e6+5,M=1e6+5,inf=0x3f3f3f3f,P=9999973; int T,n,m; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0; struct edge{int u,v,nxt;}e[M<<1]; void add(int u,int v){ e[++tot]=(edge){u,v,head[u]},head[u]=tot; } stack<int>s; bool inst[N]; int Bcnt,idx,dfn[N],low[N],bl[N]; void tarjan(int u){ dfn[u]=low[u]=++idx; s.push(u),inst[u]=1; for(int i=head[u],v;i;i=e[i].nxt){ v=e[i].v; if(!dfn[v]) tarjan(v),low[u]=Min(low[u],low[v]); else if(inst[v]&&dfn[v]<low[u]) low[u]=dfn[v]; } if(dfn[u]==low[u]){ int v; ++Bcnt; do{ v=s.top(),s.pop(); inst[v]=0,bl[v]=Bcnt; }while(u!=v); } } int main(){ freopen("4.in","r",stdin); rd(T); while(T--){ rd(n),rd(m); tot=Bcnt=idx=0; memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(bl,0,sizeof(bl)); memset(inst,0,sizeof(inst)); char a[100]; for(int i=1,pos,cnt,x,y,xx,yy;i<=m;++i){ gets(a);pos=cnt=0; while(cnt<2){ if(isdigit(a[pos])){ int b=0; while(isdigit(a[pos])) b=b*10+(a[pos]-'0'),++pos; if(!cnt) x=b; else y=b; ++cnt; } else{ if(!cnt&&a[pos]=='h') xx=0; if(!cnt&&a[pos]=='m') xx=1; if(cnt==1&&a[pos]=='h') yy=0; if(cnt==1&&a[pos]=='m') yy=1; ++pos; } } x=(x<<1)+xx,y=(y<<1)+yy; add(x,y^1),add(y,x^1); } for(int i=2;i<=(n<<1|1);++i) if(!dfn[i]) tarjan(i); int flag=0; for(int i=1;i<=n;++i) if(bl[i<<1]==bl[i<<1|1]){ flag=1;break; } if(flag) puts("BAD"); else puts("GOOD"); } return 0; }