P4171 [JSOI2010]满汉全席

[P4171 [JSOI2010]满汉全席](https://www.luogu.org/problemnew/show/P4171) 额，这个算是$2-SAT$裸题了吧。。。 $2-SAT$的图中每一条边$i->j$表示选了$i$必须选$j$。 拆点，一个点表示选，一个点表示不选，跑$Tarjan$强连通。 如果有一个点拆成的两个点在一个强联通分量里，无解；否则有解。 注：这题坑了我一下午，本来以为建图出了问题，最后发现原来$Tarjan$强连通的板子敲错了的锅，尴尬+药丸。。。 附代码： ```cpp #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define MAXN 2010 using namespace std; int n,m,c,d,top,s; int cstack[MAXN],head[MAXN],deep[MAXN],low[MAXN],colour[MAXN]; bool vis[MAXN]; struct node{ int next,to; }a[MAXN<<2]; inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } inline int change(int x){ if(x%2==0)return x-1; return x+1; } inline void add(int x,int y){ a[c].to=y;a[c].next=head[x];head[x]=c++; } void dfs(int x){ deep[x]=low[x]=d++; vis[x]=true; cstack[top++]=x; for(int i=head[x];i;i=a[i].next){ int v=a[i].to; if(!deep[v]){ dfs(v); low[x]=min(low[x],low[v]); } else if(vis[v])low[x]=min(low[x],deep[v]); } if(low[x]>=deep[x]){ s++; do{ colour[cstack[top-1]]=s; vis[cstack[top-1]]=false; }while(cstack[--top]!=x); } } void work(){ bool flag=true; for(int i=1;i<=n&&flag;i++)if(colour[(i<<1)-1]==colour[i<<1])flag=false; if(flag)printf("GOOD\n"); else printf("BAD\n"); } void init(){ c=d=top=1; s=0; memset(head,0,sizeof(head)); memset(deep,0,sizeof(deep)); memset(low,0,sizeof(low)); memset(colour,0,sizeof(colour)); memset(vis,false,sizeof(vis)); int u,v,x,y; char p,q; n=read();m=read(); for(int i=1;i<=m;i++){ cin>>p;x=read();x<<=1; if(p=='h')x--; cin>>q;y=read();y<<=1; if(q=='h')y--; u=change(x);v=change(y); add(u,y);add(v,x); } for(int i=1;i<=(n<<1);i++)if(!deep[i])dfs(i); } int main(){ int t=read(); while(t--){ init(); work(); } return 0; } ```