首先这个题，我以为是DFS。。。交上各种TLE ，RE，暴栈和超时啊。。。找了一下题解，发现是图论问题。。。唉。
又重新翻离散课本。。。定理：有向图的欧拉路连通且存在一个出度比入度大一的，存在一个入度比出度大一的，其他入度出度相等。有向图欧拉回路连通且入度出度都相等。
交上WA，然后查错，总以为是 判断是否是联通的时候做错了，其实是 忘记判断也是欧拉回路了。。。悲剧。。。代码 好烂。
#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
;
}
