Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同）
思路：欧拉路。
关于欧拉路：
(1)有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。
(2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。
（3） 无向图存在欧拉回路： 图连通，所有点都是偶数度，
（4）无向图存在欧拉路：图联通，只有两个点的度数为奇数。
有向图判断联通性判断的弱联通，因此可以用并查集实现。
具体办法是，判断根的个数，个数为大于1表示不联通。
代码实现
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
21using namespace std;
22const double eps = 1E-8;
23const int dx4[4]={1,0,0,-1};
24const int dy4[4]={0,-1,1,0};
25const int inf = 0x3f3f3f3f;
26const int N=26;
27int in[N];
28int out[N];
29int f[N];
30int root ( int x)
31{
32 if (x!=f[x]) f[x] = root(f[x]);
33 return f[x];
34}
35void merge( int x,int y)
36{
37 int rx = root(x);
38 int ry = root(y);
39 if (rx!=ry)
40 f[rx] = ry;
41}
42void init()
43{
44 for ( int i = 0 ; i < N ; i++) f[i] = i;
45 ms(in,0);
46 ms(out,0);
47}
48int n ;
49set<int>se;
50bool Euler()
51{
52 int a,b;
53 a=b=0;
54 set<int>::iterator it;
55 for ( it = se.begin() ;it!=se.end() ; it++)
56 {
57 int i = *it;
58 if (in[i]==out[i]+1)a++;
59 else if (out[i]==in[i]+1) b++;
60 else if (out[i]!=in[i]) return false;
61 }
62 if (a+b==0||(a==1&&b==1)) return true;
63 return false;
64}
65int main()
66{
67 #ifndef ONLINE_JUDGE
68 freopen("code/in.txt","r",stdin);
69 #endif
70 int T;
71 cin>>T;
72 while (T--)
73 {
74 init();
75 scanf("%d",&n);
76 se.clear();
77 for ( int i = 0 ; i < n ; i++)
78 {
79 char st[1005];
80 scanf("%s",st);
81 int len = strlen(st);
82 int u = st[0]-'a';
83 int v = st[len-1]-'a';
84 merge(u,v);
85 out[u]++;
86 in[v]++;
87 se.insert(v);
88 se.insert(u);
89 }
90 int cnt = 0 ;
91 bool die = false;
92 for (set<int>::iterator it = se.begin() ; it!=se.end() ; it++)
93 {
94 if (f[*it]==*it) cnt++;
95 if (cnt>1)
96 {
97 die = true;
98 break;
99 }
100 }
101 if (!Euler()) die = true;
102 if (die)
103 {
104 puts("The door cannot be opened.");
105 }
106 else
107 {
108 puts("Ordering is possible.");
109 }
110 }
111 #ifndef ONLINE_JUDGE
112 fclose(stdin);
113 #endif
114 return 0;
115}