首先這個題，我以為是DFS。。。交上各種TLE ，RE，暴棧和超時啊。。。找了一下題解，發(fā)現(xiàn)是圖論問題。。。唉。
又重新翻離散課本。。。定理：有向圖的歐拉路連通且存在一個出度比入度大一的，存在一個入度比出度大一的，其他入度出度相等。有向圖歐拉回路連通且入度出度都相等。
交上WA，然后查錯，總以為是 判斷是否是聯(lián)通的時候做錯了，其實是 忘記判斷也是歐拉回路了。。。悲劇。。。代碼 ?好爛。
#include <stdio.h>
#include
<
string
.h>
#include
<stdlib.h>
int
p[
27
][
27
],z,n,o[
27
],key[
27
];
int
find(
int
x)
{
int
r,t;
r
=
x;
while
(x !=
o[x])
x
=
o[x];
while
(r !=
x)
{
t
=
o[r];
o[r]
=
x;
r
=
t;
}
return
x;
}
void
merge(
int
x,
int
y)
{
x
=
find(x);
y
=
find(y);
if
(x !=
y)
o[x]
=
y;
}
int
main()
{
int
t,i,j,sum,start,end,len,sum1,sum2,k1,k2;
char
str[
1001
];
scanf(
"
%d%*c
"
,&
t);
while
(t--
)
{
z
=
1
;k1 = k2 =
0
;
memset(p,
0
,
sizeof
(p));
memset(key,
0
,
sizeof
(key));
for
(i =
1
;i <=
26
;i ++
)
o[i]
=
i;
scanf(
"
%d%*c
"
,&
n);
for
(i =
1
;i <= n;i ++
)
{
scanf(
"
%s
"
,str);
len
=
strlen(str);
start
= str[
0
] -
'
a
'
+
1
;
end
= str[len-
1
] -
'
a
'
+
1
;
key[start]
= key[end] =
1
;
merge(start,end);
p[start][end]
++
;
}
for
(i =
1
;i <=
26
;i ++
)
{
if
(key[i])
break
;
}
sum
=
find(i);
for
(j = i+
1
;j <=
26
;j ++
)
{
if
(find(j) != sum &&
key[j])
break
;
}
if
(j !=
27
)
z
=
0
;
for
(i =
1
;i <=
26
&&z;i ++
)
{
sum1
= sum2 =
0
;
for
(j =
1
;j <=
26
;j ++
)
{
sum1
+=
p[i][j];
sum2
+=
p[j][i];
}
if
(sum1 ==
sum2)
;
else
if
(sum1 == sum2+
1
)
{
k1
++
;
}
else
if
(sum1+
1
==
sum2)
{
k2
++
;
}
else
{
z
=
0
;
break
;
}
}
if
(z)
{
if
(k1==
1
&&k2==
1
)
printf(
"
Ordering is possible.\n
"
);
else
if
(k1==
0
&&k2==
0
)
printf(
"
Ordering is possible.\n
"
);
else
printf(
"
The door cannot be opened.\n
"
);
}
else
printf(
"
The door cannot be opened.\n
"
);
}
return
0
;
}
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
