Play on Words（欧拉路）

题意：给定若干个单词，若前一个的尾字母和后一个单词的首字母相同，则这两个单词可以连接，问是否所有的单词都能连接起来。

思路：欧拉路的判断，且为有向图，将每个单词的首尾字母看做节点，中间字母看做边，建图。

(1)用并查集判断图是否连通。

(2)判断奇数节点的个数为0或2个，其余节点均入度=出度。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=1010;
 4 const int M=28;
 5 int in[M];
 6 int out[M];
 7 int f[M],vis[M];
 8 void init()
 9 {
10     for (int i = 0; i < M; i ++)
11     {
12         in[i] = 0;
13         out[i] = 0;
14         f[i] = i;
15         vis[i] = 0;
16     }
17 }
18 int find(int x)
19 {
20     if (x!=f[x])
21         f[x] = find(f[x]);
22     return f[x];
23 }
24 void merge(int x,int y)
25 {
26     f[find(x)] = find(y);
27 }
28 int main()
29 {
30     int n,m;
31     scanf("%d",&n);
32     while(n--)
33     {
34         char str[N];
35         int v,u,len;
36         scanf("%d",&m);
37         init();
38         for (int i = 1; i <= m; i ++)
39         {
40             scanf("%s",str);
41             len = strlen(str);
42             u = str[0]-'a';
43             v = str[len-1]-'a';
44             vis[u] = 1;
45             vis[v] = 1;
46             in[v]++;
47             out[u]++;
48             merge(u,v);
49         }
50         int flag = 1;
51         int cnt1 = 0,cnt2 = 0;
52         int father = find(v);
53         for (int i = 0; i < M; i ++)//判断图是否连通
54         {
55             if (vis[i]&&find(i)!=father)
56             {
57                 printf("The door cannot be opened.
");
58                 flag = 0;
59                 break;
60             }
61         }
62         if(flag)//判断度数
63         {
64             for (int i = 0; i < M; i ++)
65             {
66                 if(vis[i]&&in[i]-out[i]==1)
67                     cnt1++;//入度比出度大一的节点的个数
68                 else if (vis[i]&&out[i]-in[i]==1)
69                     cnt2++;//出度比入度大一的节点的个数
70                 else if (vis[i]&&in[i]!=out[i])
71                 {
72                     flag = 0;
73                     break;
74                 }
75             }
76             if ((cnt1==1&&cnt2==1||cnt1+cnt2==0)&&flag)
77                 printf("Ordering is possible.
");
78             else
79                 printf("The door cannot be opened.
");
80         }
81 
82     }
83     return 0;
84 
85 }

View Code