这题看似简单，但蒟蒻我做起来确实花了不少功夫~ 大致题意： 给出T组数据，每一组输入两个字符串，意为要想喝后面那种饮料就必须先喝前面的，看能不能喝完所有饮料。 若能输出“Yes” else printf(“No\n”); 思路： 就是一个裸的搜环，若搜到了就直接退出，一开始的字符串就用map处理好成数字。
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<map> #include<algorithm> using namespace std; map<string,int>q; struct node{ char s[60]; }; const int maxn=100010; int to[maxn],Begin[maxn],e,Next[maxn]; void add(int x,int y){ to[++e]=y; Next[e]=Begin[x]; Begin[x]=e; } node b[20010]; char chuan1[20010]; char chuan2[20010]; bool flag1,flag2; int cnt; bool p[20010]; bool flag; void dfs(int now) { if(flag)return; for(int i=Begin[now];i;i=Next[i]){ if(p[to[i]]){ flag=1; return; } if(!p[to[i]]){ p[to[i]]=1; dfs(to[i]); p[to[i]]=0; } } } int main(){ int i,j,k,m,n,_,end1,end2,Case=0; scanf("%d",&_); while(_--){ memset(Begin,0,sizeof(Begin)); Case ++ ; memset(p,0,sizeof(p)); q.clear(); scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%s%s",chuan1,chuan2); if(!q[chuan1]) q[chuan1]=++cnt; if(!q[chuan2]) q[chuan2]=++cnt; add(q[chuan1],q[chuan2]); flag=0; for(i=1;i<=cnt;i++){ p[i]=1; dfs(i); memset(p,0,sizeof(p)); if(flag){ printf("Case %d: No\n",Case); break; } } if(!flag) printf("Case %d: Yes\n",Case); } return 0; }