poj 1386 Play on Words 有向欧拉回路

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ``acm'' can be followed by the word ``motorola''. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.

题意：给一些单词能否以某种规则排成一个序列，这个规则就是每个单词开头的字母和前一个单词最后一个字母要相同，比如motorla可以排在acm的后面或者前面。

解法：有向图的欧拉回路判断。

每个单词只能用一次，我们可以以每个单词的首尾这两个字母作为节点，每个单词作为一条边。例如motorla，m 和 a 作为节点，otorl作为连接m和a节点的一条有向边。这样，就构成了有向图。

我们在判断有向图是否有欧拉回路的时候，首先得判断图是否连通，判断图是否连通的比较好的方法就是用并查集，然后再判断欧拉回路。

有向图的欧拉回路：连通的有向图中，要么每个节点的入度和出度个数都相同，要么有一个节点的入度比出度大1，有一个节点的出度比入度大1，其余的节点入度和出度个数都相同。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 using namespace std;
 9 const int maxn=100000+10;
10 
11 struct node
12 {
13     int u,v;
14 }edge[maxn];
15 int n,father[26];
16 int vis[26],ind[26],outd[26];
17 char str[1000+10];
18 
19 int find(int x)
20 {
21     if (x==father[x]) return x;
22     return father[x]=find(father[x]);
23 }
24 
25 int main()
26 {
27     int t;
28     scanf("%d",&t);
29     while (t--)
30     {
31         scanf("%d",&n);
32         memset(vis,0,sizeof(vis));
33         memset(ind,0,sizeof(ind));
34         memset(outd,0,sizeof(outd));
35         memset(father,-1,sizeof(father));
36         for (int i=0 ;i<n ;i++)
37         {
38             scanf("%s",str);
39             int len=strlen(str);
40             int a=str[0]-'a';
41             int b=str[len-1]-'a';
42             edge[i].u=a ;edge[i].v=b ;
43             vis[a]=vis[b]=1;
44             ind[b]++ ;outd[a]++ ;
45             father[a]=a;
46             father[b]=b;
47         }
48         for (int i=0 ;i<n ;i++)
49         {
50             int u=edge[i].u;
51             int v=edge[i].v;
52             u=find(u) ;v=find(v) ;
53             if (u!=v) father[u]=v;
54         }
55         int flag=0;
56         int k;
57         for (k=0 ;k<26 ;k++) if (vis[k]) {k=find(k);break; }
58         for (int i=0 ;i<26 ;i++) if (vis[i])
59         {
60             int u=find(i);
61             if (u!=k) {flag=1;break; }
62         }
63         if (flag) {printf("The door cannot be opened.
");continue; }
64         int uu=-1,vv=-1;
65         for (int i=0 ;i<26 ;i++) if (vis[i])
66         {
67             if (outd[i]-ind[i]==1)
68             {
69                 if (uu==-1) uu=i;
70                 else flag=1;
71             }
72             else if (ind[i]-outd[i]==1)
73             {
74                 if (vv==-1) vv=i;
75                 else flag=1;
76             }
77             else if (ind[i]-outd[i]>1 || outd[i]-ind[i]>1) {flag=1;break; }
78         }
79         if (flag) {printf("The door cannot be opened.
");continue; }
80         for (int i=0 ;i<26 ;i++) if (vis[i] && i!=uu && i!=vv)
81         {
82             if (ind[i] != outd[i]) flag=1;
83         }
84         if (flag) {printf("The door cannot be opened.
");continue; }
85         else printf("Ordering is possible.
");
86     }
87     return 0;
88 }