有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。
多组数据。第一行给出数据组数T，每组数据第一行给出盘子数量N，接下去N行给出小写字母字符串，一种字符串可能出现多次。
若存在一组合法解输出“Ordering is possible.”，否则输出“The door cannot be opened.”。
时间：1s 空间：64M
1<=N<=10^5；|S|<=1000
题解：emm并查集+欧拉回路，
每一个单词有用的信息只有首尾两个字母，那么建一张图令节点表示小写字母；边表示一种单词的转移。问题就变成了在图中判断欧拉路径的存在性。
若有向图G存在欧拉路径（即为半欧拉图），那么当且仅当G的基图联通且存在顶点u
的入度比出度大1，v
的入度比出度小1，其他所有顶点的入度等于出度。
代码内有些处理细节的精妙之处。
#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<queue>#include<cmath>#include<cstring>#include<cstdlib>#include<cstdio>using namespace std;int t,n,m,c,c1,c2;char s[1005];int fa[32],u[32],v[32];int get(int x) { return x==fa[x]?x:fa[x]=get(fa[x]); }int main(){ freopen("492.in","r",stdin); freopen("492.out","w",stdout); scanf("%d",&t); while(t--){ memset(u,0,sizeof(u)); memset(v,0,sizeof(v)); scanf("%d",&n); c=c1=c2=0; for(int i=1;i<=30;i++) fa[i]=i; for(int i=1;i<=n;i++){ scanf("%s",s+1); m=strlen(s+1); int l=s[1]-'a'+1; int r=s[m]-'a'+1; fa[get(l)]=get(r); u[l]++; v[r]++; } for(int i=1;i<=26;i++) if(((u[i] || v[i]) && (get(i)==i)) || abs(u[i]-v[i])>1) c++; if(c>1){ puts("The door cannot be opened."); continue; } //连通块和出度入度不相等的个数 //这是jjj手打的！不是copy的嘤嘤嘤~ for(int i=1;i<=26;i++){ if(u[i]>v[i]) c1++; if(u[i]<v[i]) c2++; } if(c1!=c2 || c1>1) puts("The door cannot be opened."); else puts("Ordering is possible."); //printf("\n"); } return 0;}
转载于:https://www.cnblogs.com/wuhu-JJJ/p/11177361.html
