链接:http://vjudge.net/problem/viewProblem.action?id=19492

描述:单词接龙

思路:求欧拉回路或欧拉道路。

首先建图,以字母为节点,单词为边。因为单词不可能倒序,所以是有向图。

判断图的连通性,dfs就可以做到,把它当成无向图就好了。然后判断点的出入度就可以判断是不是欧拉回路或者欧拉道路。

下面是我的实现。

 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 #define Max 30
6 #define MaxLen 1010
7 int T,n,Bgn;
8 int Edge[Max][Max],Chu[Max],Ru[Max];
9 bool vis[Max];
10 char str[MaxLen];
11 inline void Get_int(int &Ret)
12 {
13 char ch;
14 bool flag=false;
15 for(;ch=getchar(),ch<'0'||ch>'9';)
16 if(ch=='-')
17 flag=true;
18 for(Ret=ch-'0';ch=getchar(),ch>='0'&&ch<='9';Ret=Ret*10+ch-'0');
19 flag&&(Ret=-Ret);
20 }
21 inline void Read()
22 {
23 Get_int(n);
24 memset(vis,false,sizeof(vis));
25 memset(Chu,0,sizeof(Chu));
26 memset(Ru,0,sizeof(Ru));
27 memset(Edge,0,sizeof(Edge));
28 int i,u,v,Len;
29 for(i=1;i<=n;i++)
30 {
31 do
32 {
33 scanf("%s",str);
34 Len=strlen(str);
35 }while(!Len);
36 u=str[0]-'a'+1; v=str[Len-1]-'a'+1;
37 //if(u==v) continue;
38 Edge[u][v]++;Edge[v][u]++;
39 Chu[u]++;Ru[v]++;
40 vis[u]=vis[v]=true;
41 }
42 Bgn=u;
43 }
44 void Dfs(int u)
45 {
46 vis[u]=false;
47 for(int i=1;i<=26;i++)
48 if(Edge[u][i]&&vis[i])
49 Dfs(i);
50 }
51 inline bool Solve()
52 {
53 int i,ch=0,ru=0;
54 Dfs(Bgn);
55 for(i=1;i<=26;i++)
56 {
57 if(vis[i])
58 return false;
59 if(Chu[i]!=Ru[i])
60 {
61 if(Chu[i]-Ru[i]==1)
62 ch++;
63 else if(Ru[i]-Chu[i]==1)
64 ru++;
65 else
66 return false;
67 }
68 }
69 if((ch==1&&ru==1)||(ch==0&&ru==0))
70 return true;
71 return false;
72 }
73 int main()
74 {
75 Get_int(T);
76 while(T--)
77 {
78 Read();
79 if(Solve())
80 printf("Ordering is possible.\n");
81 else
82 printf("The door cannot be opened.\n");
83 }
84 return 0;
85 }

最新文章

  1. 前端打包构建工具gulp快速入门
  2. Swift - 进度条(UIProgressView)的用法
  3. Mysql逻辑模块组成
  4. ASP.NET MVC 控制器向View传值的三种方法
  5. memwatch
  6. Javascript使用function创建类的两种方法
  7. (转载)UITableView的详细讲解
  8. .net之单元测试
  9. Android 再按一次退出程序
  10. Java线程状态:BLOCKED与WAITING的区别
  11. lua5.1 和 5.2 关于 sequence 的定义变化,对#table取值的影响
  12. 基于AngularJS的前端云组件最佳实践
  13. Docker 单主机网络
  14. 《Java大学教程》--第1章 步入Java世界
  15. JAVA spring 常用包作用详解(转)
  16. 浅尝一致性Hash原理
  17. 带你从零学ReactNative开发跨平台App开发(十一)
  18. 建立ARM交叉编译环境 (arm-none-linux-gnueabi-gcc with EABI)【转】
  19. DeveloperAppleHelp
  20. 风雪之隅(Laruence PHP开发组成员, Zend兼职顾问, Yaf, Yar, Yac, Opcache等项目作者、维护者.)

热门文章

  1. Typecho 如何安装主题和插件
  2. VUE3 之 组件传参
  3. gin中绑定查询字符串或表单数据
  4. while...break 实例
  5. 双系统之删除Linux以及grub的引导
  6. svn 用户名,密码 查看/删除
  7. php栈的定义及入栈出栈的实现 算法
  8. WJMZBMR(陈立杰)在成都赛区开幕式上的讲话
  9. 利用redis+AOP简单处理MQ冥等问题
  10. shell——eval exec