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