HDU 1116 Play on Words
这个题目要运用到欧拉路得相关知识，并且也要并查集，题目说的是：给你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
补充：软件开发 , C语言 ,
