思路:

分别存下每个字符串的首尾字符,以字符为结点,单词看作一条变,就变成了求欧拉回路了,先判断下图是否连通,然后根据欧拉回路的结论:最多只能有两个点的入读不等于初读,而且必须是一个点的出度恰好比入度大1(将它作为起点),另一个的入度比出度大1(将它作为终点);

实现代码:

#include<iostream>
#include<cstring>
using namespace std;
const int M = ;
int f[M];
int in[M],out[M];
int fd(int x) {return f[x]==x? x:f[x]=fd(f[x]);}
void mix(int a,int b) {a=fd(a);b=fd(b);if(a!=b) f[a]=b;}
void init(){
for(int i = ;i <= M;i ++){
f[i] = i;
}
memset(in,,sizeof(in));
memset(out,,sizeof(out));
} int main()
{
string s;
int t,n;
cin>>t;
while(t--){
init();
cin>>n;
for(int i = ;i < n;i ++){
cin>>s;
int len = s.size();
int x = s[] - 'a';
int y = s[len-] - 'a';
in[x]++; out[y]++;
//cout<<x<<" "<<y<<endl;
mix(x,y);
}
int ans = ;
for(int i = ;i < ;i ++){
if(i==f[i]&&(in[i]||out[i])){
ans++;
}
}
//cout<<ans<<endl;
bool flag = true;
int num1 = ,num2 = ;
if(ans == ){
for(int i=;i<=;i++){
if(in[i]!=out[i]){
if(in[i]+==out[i]) num1++;
else if(in[i]==out[i]+) num2++;
else{
flag = false;break;
}
}
}
if(num1&&num2&&num1+num2>) flag = false;
}
else flag = false;
if(flag) cout<<"Ordering is possible."<<endl;
else cout<<"The door cannot be opened."<<endl;
}
return ;
}

最新文章

  1. iOS播放器 - AVPlayer
  2. 开启MySQL日志
  3. hdu 4049 2011北京赛区网络赛J 状压dp ***
  4. Oracle列操作(增加列,修改列,删除列)
  5. Eclipse设置选中高亮显示(包含debug)
  6. c#基础--常量(const),只读字段(readonly)
  7. android2.3 View视图框架源码分析之一:android是如何创建一个view的?
  8. iis7.0/8.0rewrite规则
  9. Java 过滤器的作用
  10. 如何配置Spring的XML文件及使用
  11. 如何在linux上构建objective-c程序
  12. Spring+Hibernate实现动态SessionFactory切换(改进版)
  13. 简单搭建一个SpringBoot
  14. Elasticsearch 关键字:索引,类型,字段,索引状态,mapping,文档
  15. GRADLE下运行main函数/执行测试用例
  16. logstash-1-安装配置
  17. 20155314 2016-2017-2 《Java程序设计》第5周学习总结
  18. 二叉搜索树的第k大的节点
  19. Deep Residual Learning for Image Recognition(残差网络)
  20. js与jQuery实现方式对比汇总

热门文章

  1. Scala--文件和正则表达式
  2. mysql事务,select for update,及数据的一致性处理
  3. 汇编 inc 和 dec 指令
  4. Linux中tty、pty、pts的概念区别 转载
  5. html元素双击事件触发机制猜想及疑惑
  6. Python_Xlrd&amp;Xlwt
  7. Jenkins报表 代码 指标分析
  8. Linux 第三周 学习笔记和实验
  9. C语言版本:顺序表的实现
  10. 《Gogoing》Alpha版使用说明