題意 ： 有很多門，每個門上有很多磁盤，每個盤上一個單詞，必須重新排列磁盤使得每個單詞的第一個字母與前一個單詞的最后一個字母相同。給你一組單詞問能不能排成上述形式。
思路 ：把每個單詞看成有首字母指向尾字母的有向邊，每個字母看成一個點，題中要求等效于判斷圖中是否存在一條路徑經過每一條一次且僅一次，就是有向歐拉通路。統計個頂點的出入度，如果每個點的出入度都相同，那就是歐拉回路，如果有兩個奇數度，那就是歐拉通路，除此之外，都不能滿足要求。還有別忘了判斷是否連通，此時用到并查集，圖中所有的邊（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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
