题意 ： 有很多门，每个门上有很多磁盘，每个盘上一个单词，必须重新排列磁盘使得每个单词的第一个字母与前一个单词的最后一个字母相同。给你一组单词问能不能排成上述形式。
思路 ：把每个单词看成有首字母指向尾字母的有向边，每个字母看成一个点，题中要求等效于判断图中是否存在一条路径经过每一条一次且仅一次，就是有向欧拉通路。统计个顶点的出入度，如果每个点的出入度都相同，那就是欧拉回路，如果有两个奇数度，那就是欧拉通路，除此之外，都不能满足要求。还有别忘了判断是否连通，此时用到并查集，图中所有的边（u，v），如果u!=v且属于不同的连通分量，就合并。 欧拉回路的基本定理及概念。
1
#include <cstdio>
2
#include <cstring>
3
#include <iostream>
4
5
using
namespace
std ;
6
7
char
word[
1001
] ;
8
int
father[
27
],
out
[
27
],
in
[
27
] ,vis[
30
];
9
10
int
find_(
int
x)
11
{
12
if
(father[x] !=
x)
13
father[x] =
find_(father[x]) ;
14
return
father[x] ;
15
}
16
17
void
mergee(
int
a,
int
b)
18
{
19
if
(find_(a) !=
find_(b))
20
father[find_(a)] =
find_(b) ;
21
}
22
23
void
Init()
24
{
25
memset(
out
,
0
,
sizeof
(
out
)) ;
26
memset(
in
,
0
,
sizeof
(
in
)) ;
27
for
(
int
i =
0
; i <
26
; i++
)
28
father[i] =
i ;
29
memset(vis,
0
,
sizeof
(vis)) ;
30
}
31
32
int
main()
33
{
34
int
T ;
35
cin >>
T ;
36
int
n ;
37
while
(T--
)
38
{
39
cin >>
n ;
40
Init() ;
41
while
(n --
)
42
{
43
scanf(
"
%s
"
,word) ;
44
int
u = word[
0
]-
'
a
'
;
45
int
v = word[strlen(word)-
1
]-
'
a
'
;
46
mergee(u,v) ;
47
out
[u] ++
;
48
in
[v] ++
;
49
vis[u] = vis[v] =
1
;
50
}
51
int
cnt =
0
,cnt1 =
0
,cnt2 =
0
;
52
for
(
int
i =
0
; i <
26
; i++
)
53
{
54
if
(vis[i] && father[i] ==
i)
55
{
56
cnt ++
;
57
}
58
}
59
if
(cnt >
1
)
60
{
61
puts(
"
The door cannot be opened.
"
) ;
62
continue
;
63
}
64
bool
flag =
true
;
65
for
(
int
i =
0
; i <
26
; i++
)
66
{
67
if
(vis[i] &&
out
[i] !=
in
[i])
68
{
69
if
(
out
[i]-
in
[i] ==
1
)
70
{
71
cnt1 ++
;
72
if
(cnt1 >
1
)
73
{
74
flag =
false
;
75
break
;
76
}
77
}
78
else
if
(
in
[i]-
out
[i] ==
1
)
79
{
80
cnt2 ++
;
81
if
(cnt2 >
1
)
82
{
83
flag =
false
;
84
break
;
85
}
86
}
87
else
88
{
89
flag =
false
;
90
break
;
91
}
92
}
93
}
94
if
(!flag) puts(
"
The door cannot be opened.
"
) ;
95
else
puts(
"
Ordering is possible.
"
) ;
96
}
97
return
0
;
98
}
