/*
题意:单词拼接,前一个单词的末尾字母和后一个单词的开头字母相同
思路:将一个单词的开头和末尾单词分别做两个点并建一条有向边!然后判断是否存在欧拉回路或者欧拉路 再次强调有向图欧拉路或欧拉回路的判定方法:
(1)有向图G为欧拉图(存在欧拉回路),当且仅当G的基图连通,且所有顶点的入度等于出度。
(2)有向图G为半欧拉图(存在欧拉道路),当且仅当G的基图连通,且存在顶点u的入度比出度大1、v的入度比出度小1,
其它所有顶点的入度等于出度(顶点u,v的个数必须都是1)。 求该图的连通性的时候,只要求该有向图是弱连通的就可以了!所以转换为无向图的连通问题!
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; int g[][];
char ch[];
int vis[], used[];
int inD[], outD[]; void dfs(int u){
vis[u]=;
for(int i=; i<; ++i)
if(g[u][i] && !vis[i])
dfs(i);
} bool checkDeg(){
int inOut=, outIn=;
for(int i=; i<; ++i)
if(used[i] && inD[i]-outD[i]!=){
if(inD[i]-outD[i]> || inD[i]-outD[i]<-) return false;
else inD[i]-outD[i]> ? ++inOut : ++outIn;
}
return (inOut== && outIn==) || (inOut== && outIn==);
} int main(){
int n, t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
memset(vis, , sizeof(vis));
memset(used, , sizeof(used));
memset(g, , sizeof(g));
memset(inD, , sizeof(inD));
memset(outD, , sizeof(outD));
while(n--){
scanf("%s", ch);
int u=ch[]-'a', v=ch[strlen(ch)-]-'a';
g[u][v]=g[v][u]=;//无向图的连通性 即是有向图的弱连通
used[u]=used[v]=;
++inD[v];
++outD[u];
}
bool flag=true;
for(int i=; i<; ++i)
if(used[i]){
dfs(i);
break;
}
for(int i=; i<; ++i)
if(used[i] && !vis[i]){
flag=false;
break;
}
if(flag && !checkDeg())
flag=false;
if(flag)
printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
return ;
}

最新文章

  1. ASP.NET: 正在中止线程 错误原及解决方法
  2. iOS开发,系统自带的分享简单实现
  3. Python:if __name__ == &#39;__main__&#39;
  4. android:inputType参数类型说明
  5. hiho #1288 微软2016.4校招笔试题 Font Size
  6. Swapping
  7. Payment Terms 收付款条件和分期付款设置
  8. win7重新安装win7
  9. SOA基础
  10. 循环与range
  11. Redis4- llist的操作
  12. CentOS 7 上面安装PowerShell
  13. 2017JAVA课程设计
  14. 为什么选择Django?
  15. Mysql之视图的操作
  16. ArcGIS API for JavaScript 入门教程[6] 再讲数据——Map类之可操作图层
  17. 严重: The web application [] registered the JDBC driver [com.microsoft.sqlserver.jdbc.SQLServerDriver] but failed to unregister it when the web application was stopped. To prevent a memory leak, the JDB
  18. 服务器搭建--Linux安装rabbitmq
  19. poj_2182 线段树/树状数组
  20. Shell 命令行,实现一个获取任意位数的随机密码的脚本

热门文章

  1. Android 百度云媒体 等播放器播放4:3等多种比例的视频 大小配置的问题
  2. 三星(SAMSUNG)910S3L-K04 安装win7的BIOS设置
  3. ORA-12705问题解决过程
  4. Cannot refer to an instance field pageTitle while explicitly invoking a cons
  5. 创建一个ArcGIS for Android 新项目并显示出本地的地图
  6. I am Nexus Master!(虽然只是个模拟题。。。但仍想了很久!)
  7. 【腾讯Bugly干货分享】微信读书iOS性能优化
  8. UWP开发随笔——UWP新控件!AutoSuggestBox!
  9. 【吉光片羽】奇怪的Bug-细节的问题
  10. [Voice communications] 让音乐响起来