acwing1185. 单词游戏(欧拉图)「建议收藏」

acwing1185. 单词游戏(欧拉图)「建议收藏」有 N 个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序,判断是否能达到这一要求。输入格式第一行包含整数 T,表示共有 T 组测试数据。每组数据第一行包含整数 N,表示盘子数量。接下来 N 行,每行包含一个小写字母字符串,表示一个盘子上的单词。一个单词可能出现多次。输出格式如果存在合法解,则输出”Ordering is possible.”,否则输出”The

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168588.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • “备份集中的数据库备份与现有的数据库不同”解决方法「建议收藏」

    “备份集中的数据库备份与现有的数据库不同”解决方法「建议收藏」原文发布时间为:2010-09-16——来源于本人的百度文章[由搬家工具导入]最主要就是要在“选项”中选择“覆盖现有数据库”,否则就会出现“备份集中的数据库备份与现有的数据库”的问题。以前一直使用SQLServer2000,现在跟潮流都这么紧,而且制定要求使用SQLServer2005,就在现在的项目中使用它了。对于SQLServer2005,有几个地方是要注意的,比方在还原数据库…

  • 使用 EasyPOI 优雅导出Excel模板数据(含图片)

    点击上方“全栈程序员社区”,星标公众号 重磅干货,第一时间送达 作者:星悬月 blog.csdn.net/u012441819/article/details/96828044 E…

  • csgo开箱网站可以取回的_csgo官方开箱网站在哪里

    csgo开箱网站可以取回的_csgo官方开箱网站在哪里Incsgo,能取回的开箱网.我们为Incsgo爱好者们倾力打造品质卓越的Incsgo开箱平台,Incsgo抽奖网站,安全可靠,玩法多样。立即注册领取奖金,库存充足,全新箱子,一秒取回。Incsgo官方网站-能够取回的csgo开箱子网站官方链接:www.incsgo.gg注册登录自动免费获得$1.00美金优惠码:csgogo(充值使用csgogo可增加5%充值金额)支付:微信支付宝状态:直接取回…

  • 关系数据库设计理论中,起核心作用的是_关系数据库设计理论主要包括

    关系数据库设计理论中,起核心作用的是_关系数据库设计理论主要包括关系数据库设计理论设计一个好的关系数据库系统,关键是要设计一个好的数据库模式(数据库逻辑设计问题)数据库逻辑设计主要解决的问题关系数据库应该组织成几个关系模式关系模式中包括哪些属性“不好”的数据库设计举例:为学校设计一个关系数据库关系模式:UN(Sno,Cno,G,Sdept,MN)Sno:描述学生Sdept:描述系名MN:描述系…

    2022年10月16日
  • LoadRunner11.00安装&使用教程[通俗易懂]

    LoadRunner11.00安装&使用教程[通俗易懂]本教程分为四部分内容:安装序言:由于LoadRunner12.02或者12.53版本是HP公司推出的自带免费50个虚拟用户进行压力测试的版本,目的为了工程师去学习与了解的该工具。为了增大压力(增加虚拟用户数)到达高并发的性能测试,采用LoadRunner11.00,增加对应的Lice…

  • linux mysql 软连接_linux 软连接的使用[通俗易懂]

    linux mysql 软连接_linux 软连接的使用[通俗易懂]软连接是linux中一个常用命令,它的功能是为某一个文件在另外一个位置建立一个同不的链接。具体用法是:ln-s源文件目标文件。当我们需要在不同的目录,用到相同的文件时,我们不需要在每一个需要的目录下都放一个必须相同的文件,我们只要在其它的目录下用ln命令链接(link)就可以,不必重复的占用磁盘空间。例如:ln-s/usr/local/mysql/bin/mysql/usr/bin…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号