大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。
你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。
请你编写一个程序，判断是否能达到这一要求。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 N，表示盘子数量。
接下来 N 行，每行包含一个小写字母字符串，表示一个盘子上的单词。
一个单词可能出现多次。
输出格式
如果存在合法解，则输出”Ordering is possible.”，否则输出”The door cannot be opened.”。
数据范围
1≤N≤105,
单词长度均不超过1000
输入样例：
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
输出样例：
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
题解
欧拉回路
#include<bits/stdc++.h>
using namespace std;
const int N = 26;
int f[N],in[N],out[N],vis[N];
int find(int x){
return f[x] = (x == f[x] ? f[x] : find(f[x]));
}
int main(){
int T;
scanf("%d",&T);
int n;
while(T --){
memset(in,0,sizeof in);
memset(out,0,sizeof out);
memset(vis,0,sizeof vis);
for(int i = 0;i < 26;i ++)f[i] = i;
scanf("%d",&n);
char s[1010];
while(n --){
scanf("%s",s);
int a = s[0] - 'a',b = s[strlen(s) - 1] - 'a';
in[b] ++ ,out[a] ++;
f[find(a)] = find(b);
vis[a] = vis[b] = true;
}
int l = 0,h = 0;
bool f = true;
for(int i = 0;i < 26;i ++){
if(in[i] != out[i]){
if(in[i] == out[i] + 1)l ++;
else if(in[i] == out[i] - 1)h ++;
else f = false;
}
}
if(f && ((l != 1 || h != 1) && !(l == 0 && h == 0)))f = false;
int p = -1;
for(int i = 0;i < 26;i ++){
if(vis[i]){
if(p == -1)p = find(i);
else if(find(i) != p){
f = false;
break;
}
}
}
if(!f)cout<<"The door cannot be opened."<<endl;
else cout<<"Ordering is possible."<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168588.html原文链接：https://javaforall.net
