有向圖是否具有歐拉通路或回路的判定:
歐拉通路:圖連通；除2個端點外其余節(jié)點入度=出度；1個端點入度比出度大1；一個端點入度比出度小1 或 所有節(jié)點入度等于出度
歐拉回路:圖連通；所有節(jié)點入度等于出度
#include<stdio.h>
#include
<
string
.h>
#define
MAX 27
int
in
[MAX],
out
[MAX];
int
visit[MAX],father[MAX];
int
find(
int
index)
{
if
(index==father[index])
return
index;
else
return
find(father[index]);
}
int
main(
void
)
{
int
t,n;
int
i,j;
int
s,e;
char
str[
1001
];
scanf(
"
%d
"
,&
t);
while
(t--
)
{
scanf(
"
%d
"
,&
n);
memset(visit,
0
,
sizeof
(visit));
memset(
in
,
0
,
sizeof
(
in
));
memset(
out
,
0
,
sizeof
(
out
));
for
(i=
0
;i<MAX;i++) father[i]=
i;
for
(i=
0
;i<n;i++
){
scanf(
"
%s
"
,str);
int
len=
strlen(str);
s
=str[
0
]-
'
a
'
,e=str[len-
1
]-
'
a
'
;
father[s]
=father[e]=
find(s);
visit[s]
=visit[e]=
1
;
out
[s]++;
in
[e]++
;
}
//
判斷改圖是否連通
int
r=
0
;
for
(i=
0
;i<MAX;i++
){
if
(visit[i]&&i==father[i]) r++
;
}
if
(r>
1
){
//
aba abc
printf(
"
The door cannot be opened.\n
"
);
continue
;
}
int
x,y,z,h;
x
=y=z=h=
0
;
for
(i=
0
;i<MAX;i++
){
if
(visit[i]){
if
(
out
[i]-
in
[i]==
1
==
1
) x++
;
else
if
(
in
[i]-
out
[i]==
1
)y++
;
else
if
(
in
[i]==
out
[i]) z++
;
else
h++
;
}
}
if
(h==
0
&&((x==
1
&&y==
1
)||(x==
0
||y==
0
))) printf(
"
Ordering is possible.\n
"
);
else
printf(
"
The door cannot be opened.\n
"
);
}
return
0
;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
