题意:

输入n(n≤100000)个单词,是否可以把所有这些单词排成一个序列,使得每个单词的第一个字母和上一个单词的最后一个字母相同(例如acm、malform、mouse)。每个单词最

多包含1000个小写字母。输入中可以有重复单词。

分析:

可以看出, 把字母看成顶点(最多26个), 然后单词就是有向边, 单词与单词之间的关系就连接起来了, 然后建立邻接矩阵, 自环的可以忽略, 记录输入的字母有哪几个, 字母的度数。

然后图中存在欧拉通路的条件有2个

(1) 连通(我用了dfs来判断)

(2) 要么没有奇度顶点, 如果有, 那么肯定是有一个入度-出度=1 有一个入度-出度= -1。

用好这两个条件就可以判定应该就可以得出答案了

 #include <bits/stdc++.h>
using namespace std;
int degree[],used[];//度数 有没有使用过
int G[][];// 邻接矩阵
int n;
int id(int a){
return a-'a';
}
int vis[];
void dfs(int u){
vis[u] = ;
for(int i = ; i < ; i++){
if(G[u][i] && !vis[i]){
dfs(i);
}
}
} bool judge(){
int num1 = , num2 = ;
int u = , v;
for(int i = ; i< ; i++){
if(used[i]){
u = i;//u一开始等于图中任意一个顶点
break;
}
}
for(int i = ; i < ; i++){
if(used[i]){
if(degree[i] != ){
if(degree[i] == ) {num1++; u = i;}//此时u就要等于入度>出度的顶点了
else if(degree[i] == -){num2++; v = i;}
else return false;
}
}
}
if((num1 || num2) && num1 + num2 != ) return false;//如果有 而且不是只有2个 就可以判为false了 memset(vis,,sizeof(vis));
dfs(u);
for(int i = ; i < ; i++){
if(used[i] && !vis[i]){//如果有这个点, 遍历又没遍历到 false;
return false;
}
}
return true; }
int main(){
int T;
scanf("%d", &T);
while(T--){
memset(degree,,sizeof(degree));
memset(used,,sizeof(used));
memset(G,,sizeof(G));
scanf("%d", &n);
for(int i = ; i < n; i++){
char s[];
scanf("%s", s);
int s1 = s[] , s2 = s[strlen(s)-];
if(s1 != s2){
G[id(s1)][id(s2)] = ;
}
used[s1 -'a'] = ;
used[s2 -'a'] = ;
degree[id(s1)]++;//出度++
degree[id(s2)]--;//入度--
}
// for(int i = 0; i<26; i++){//观察度数
// if(used[i])
// printf("%c %d\n", i+'a', degree[i]);
// }
printf("%s\n", judge()? "Ordering is possible.":"The door cannot be opened.");
}
}

最新文章

  1. mmap为什么比read/write快(兼论buffercache和pagecache)
  2. 排序图解:js排序算法实现
  3. 关于IOC的思考
  4. webssh software
  5. ASP.NET MVC 3 配置EF自动生成模型
  6. OAUTH协议简介
  7. caffe训练超参数
  8. 对百度WebUploader的二次封装,精简前端代码之图片预览上传(两句代码搞定上传)
  9. 「雅礼集训 2017 Day5」珠宝
  10. Mysql数据库表被锁定处理
  11. spring-mvc.xml与spring-mybatis.xml配置文件中命名空间问题
  12. (转)percona的安装、启动、停止
  13. 【刷题】LOJ 6011 「网络流 24 题」运输问题
  14. 转:ubuntu 下GPU版的 tensorflow / keras的环境搭建
  15. oracle 杀掉当前用户的进程
  16. Why We Worry and What to Do About It
  17. app瘦身和包压缩技术有什么区别?
  18. 【python常见面试题】之python 中对list去重的多种方法
  19. BZOJ4415:[SHOI2013]发牌(线段树)
  20. malloc和new的区别 begin

热门文章

  1. 【原创】《从0开始学Elasticsearch》—初识Elasticsearch
  2. Hdu 4465 Candy (快速排列组合+概率)
  3. hdu 1863 畅通工程(Kruskal+并查集)
  4. Rocketmq Broker启动网卡顺序问题
  5. String的用法——获取功能
  6. vue-cli 3 配置打包环境
  7. CCF|打酱油|Java
  8. 【Python】第一个爬虫
  9. 计算器Pro应用项目源码
  10. php常用的一些代码