频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
HDU 1116 Play on Words
2011-07-19 10:27:22           
收藏   我要投稿

这个题目要运用到欧拉路得相关知识,并且也要并查集,题目说的是:给你n个单词,要你判断这些单词能不能首尾相连。
理解题目意思后,进行转化,输入字符串,提取首位字母作为下标来表示两节点的出现,以及相对应节点入度和出度的增加,
转化为并查集的应用即可。那么从可以想象一幅由首位字母节点构成的图,当且仅当图是一条欧拉回路或者欧拉通路的时候,
才能满足题目的要求,至于欧拉回路和欧拉通路的判定可以总结为如下:
1)所有的点联通
2)欧拉回路中所有点的入度和出度一样。
3)欧拉通路中起点的入度 - 出度 = 1,终点的 初度 - 入度 = 1, 其他的所有点入度 = 出度;

有了上面这些知识点做铺垫,相信理解起来就比较容易了,下面我的代码:  1 #include<stdio.h>  
 2 #include<string.h>  
 3 #include<math.h>  
 4 #define N 30  
 5 /*
 6 欧拉回路,所有点连通,并且所有点的入度等于出度。
 7 欧拉通路。从原点 S出发,经过所有点,从终点 t出去。
 8 所有点除起点终点外的度都是偶数,且出度等于入度
 9 起点的出度比入度大 1
10 终点的入度比出度大 1
11 */
12
13 int father[N],vis[N]; 
14 //father[i] 表示节点 i 的 BOSS ! vis[i]表示节点 i 出现过!
15 int findx(int x) 
16 {  //找节点  x 的 BOSS !
17     if(father[x]!=x) 
18         father[x]=findx(father[x]); 
19     return father[x]; 
20 } 
21 void merge(int a,int b) 
22 {  // 合并 节点 a 和节点 b !
23     int x,y; 
24     x=findx(a); 
25     y=findx(b); 
26     if(x!=y) father[x]=y; 
27 } 
28 int main() 
29 { 
30     int text,cnt,i,j,n,out[N],in[N],p[30],a,b; 
31     char str[1001]; 
32     scanf("%d",&text); 
33     while(text--) 
34     { 
35         scanf("%d",&n); 
36         memset(out,0,sizeof(out)); 
37         memset(in,0,sizeof(in)); 
38         memset(vis,0,sizeof(vis)); 
39         for(i=0;i<26;i++) 
40             father[i]=i;  //初始化数组
41         while(n--) 
42         {  // 处理所给信息 !
43             scanf("%s",str); 
44             a=str[0]-'a'; 
45             b=str[strlen(str)-1]-'a'; 
46             merge(a,b); 
47             out[a]++; 
48             in[b]++;  // 记录节点 a 和 b的入度和出度
49             vis[a]=1; 
50             vis[b]=1; //标记节点 a 和 b的出现
51         } 
52         for(i=0;i<26;i++) 
53             father[i]=findx(i);  //找出每个节点的 BOSS 
54         for(cnt=0,i=0;i<26;i++) 
55             if(vis[i] && father[i]==i) 
56                 cnt++;  // 统计最终 BOSS 即根节点的个数 。
57         if(cnt>1)  //图不连通  
58         { 
59             printf("The door cannot be opened.\n"); 
60             continue; 
61         } 
62          
63         for(j=0,i=0;i<26;i++) 
64             if(vis[i] && out[i]!=in[i]) 
65                 p[j++]=i;  //统计入度和出度不相等的点的信息
66         if(j==0)  
67         {//欧拉回路,即环  
68             printf("Ordering is possible.\n"); 
69             continue; 
70         } 
71         if(j==2 && ( out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1 
72             || out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1 ) ) 
73         {//欧拉通路  
74             printf("Ordering is possible.\n"); 
75             continue; 
76         } 
77         printf("The door cannot be opened.\n"); 
78     } 
79     return 0; 
80 } 
81

点击复制链接 与好友分享!回本站首页
相关TAG标签 HDU Play on Words
上一篇:qt获取文件—超大图标
下一篇:HDU 1162 Eddy's picture
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站