| 试题描述 |
| 有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。 |
| 输入 |
| 多组数据。第一行给出数据组数 T，每组数据第一行给出盘子数量 N，接下去 N 行给出小写字母字符串，一种字符串可能出现多次。 |
| 输出 |
| 若存在一组合法解输出Ordering is possible.，否则输出The door cannot be opened.。 |
| 输入示例 |
| 32acmibm3acmmalformmouse2okok |
| 输出示例 |
| The door cannot be opened.Ordering is possible.The door cannot be opened. |
| 其他说明 |
| 数据范围与提示 1≤N≤10^5,∣S∣≤1000 |
有向图欧拉路径的定义：联通并且除了起点和终点，其他的节点的入度等于出度，起点的出度比入度多1，终点的入度比出度多1
然后算法的话，用并查集维护联通，入度和出度在输入的时候开两个数组记录
下面给出代码：
#include#include #include #include #include #include #include using namespace std;inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ;}int T,n;char a[1006];int in[106],out[106];int f[106];int getf(int v){ if(f[v]==v) return v; return f[v]=getf(f[v]);}int main(){ T=rd(); while(T--){ memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=1;i<=26;i++) f[i]=i; n=rd(); for(int i=1;i<=n;i++){ scanf("%s",a+1); int len=strlen(a+1); int x=a[1]-'a'+1,y=a[len]-'a'+1; out[x]++,in[y]++; int h1=getf(x),h2=getf(y); if(h1!=h2) f[h2]=h1; } int num=0; int set1,set2; for(int i=1;i<=26;i++){ if(in[i]!=out[i]){ num++; set2=set1; set1=i; } } if(num>2||num==1){ printf("The door cannot be opened.\n"); continue; } if(num==2){ if(!(in[set1]==out[set1]+1&&in[set2]==out[set2]-1)&&!(in[set1]==out[set1]-1&&in[set2]==out[set2]+1)){ printf("The door cannot be opened.\n"); continue; } } int cnt=0; for(int i=1;i<=26;i++){ if(in[i]+out[i]==0) continue; if(f[i]==i) cnt++; } if(cnt==0||cnt>1) printf("The door cannot be opened.\n"); else printf("Ordering is possible.\n"); } return 0;}