感谢 这里 。
test4确实是个不连通的case，奇怪的是我用check函数跟if (check() == false)来判断这个case，当不连通时就死循环，得到的结果是不一样的，前者得到WA，后者得到TLE，难道SGU能自动在某个条件下终止死循环，然后返回false吗。
不连通的情况FIX了，修改了代码如下：
#include <iostream>
#include
<vector>
#include
<
string
>
#include
<queue>
#include
<map>
#include
<
string
.h>
using
namespace
std;
class
Edge {
public
:
int
no, u, v;
char
d;
Edge reverse() {
Edge rev;
rev.no
=
no;
rev.u
=
v;
rev.v
=
u;
rev.d
=
'
-
'
;
return
rev;
}
};
class
Graph {
private
:
map
<
int
,
int
>
u2i;
vector
<vector<Edge> >
G;
int
deg[
210
], n, no, use[
105
], vUse[
210
];
vector
<Edge>
solution;
public
:
Graph(vector
<Edge>&
edges) {
n
=
edges.size();
makeU2I(edges);
memset(deg,
0
,
sizeof
(deg));
G.clear();
G.resize(no);
for
(
int
i =
0
; i < edges.size(); i++
) {
G[u2i[edges[i].u]].push_back(edges[i]);
G[u2i[edges[i].v]].push_back(edges[i].reverse());
deg[u2i[edges[i].u]]
++
;
deg[u2i[edges[i].v]]
++
;
}
}
void
makeU2I(vector<Edge>&
edges) {
u2i.clear();
for
(
int
i =
0
; i < edges.size(); i++
) {
u2i[edges[i].u]
= u2i[edges[i].v] =
0
;
}
no
=
0
;
for
(map<
int
,
int
>::iterator it = u2i.begin(); it != u2i.end(); it++
) {
it
->second = no++
;
}
}
int
solve() {
int
beg = -
1
, end = -
1
;
for
(
int
i =
0
; i < no; i++
) {
if
(deg[i] &
1
) {
if
(beg == -
1
) {
beg
=
i;
}
else
if
(end == -
1
) {
end
=
i;
}
else
{
return
-
1
;
}
}
}
if
(beg == -
1
) {
beg
=
0
;
}
memset(use,
0
,
sizeof
(use));
dfs(beg);
return
0
;
}
bool
dfs(
int
u) {
for
(
int
i =
0
; i < G[u].size(); i++
) {
if
(use[G[u][i].no] ==
0
) {
use[G[u][i].no]
=
1
;
if
(dfs(u2i[G[u][i].v])) {
solution.push_back(G[u][i]);
return
true
;
}
else
{
use[G[u][i].no]
=
0
;
}
}
}
for
(
int
i =
1
; i <= n; i++
) {
if
(use[i] ==
0
) {
return
false
;
}
}
return
true
;
}
void
check(
int
n) {
if
(solution.size() !=
n) {
while
(
1
);
}
for
(
int
i =
0
; i < solution.size() -
1
; i++
) {
/*
printf("%d %d, %d %d\n",
solution[i].getU(), solution[i].getV(),
solution[i + 1].getU(), solution[i + 1].getV());
*/
//
if (solution[i].getV() != solution[i + 1].getU()) {
if
(solution[i].v != solution[i +
1
].u) {
while
(
1
);
}
}
}
bool
check2(
int
n) {
if
(solution.size() !=
n) {
while
(
1
);
return
false
;
}
else
{
return
true
;
}
}
bool
checkConnectity() {
memset(vUse,
0
,
sizeof
(vUse));
vector
<
int
>
Q;
Q.push_back(
0
);
vUse[
0
] =
1
;
for
(
int
i =
0
; i < Q.size(); i++
) {
for
(
int
j =
0
; j < G[Q[i]].size(); j++
) {
if
(vUse[u2i[G[Q[i]][j].v]] ==
0
) {
vUse[u2i[G[Q[i]][j].v]]
=
1
;
Q.push_back(u2i[G[Q[i]][j].v]);
}
}
}
for
(
int
i =
0
; i < no; i++
) {
if
(vUse[i] ==
0
) {
return
false
;
}
}
return
true
;
}
void
getSolution() {
//
for (int i = 0; i < solution.size(); i++) {
for
(
int
i = solution.size() -
1
; i >=
0
; i--
) {
printf(
"
%d %c\n
"
, solution[i].no, solution[i].d);
}
}
};
int
main()
{
int
n;
scanf(
"
%d
"
, &
n);
vector
<Edge>
edges;
for
(
int
i =
0
; i < n; i++
) {
int
a, b;
scanf(
"
%d%d
"
, &a, &
b);
Edge e;
e.no
= i +
1
;
e.u
= a; e.v =
b;
e.d
=
'
+
'
;
edges.push_back(e);
}
Graph graph(edges);
if
(graph.solve() == -
1
|| graph.checkConnectity() ==
false
) {
printf(
"
No solution\n
"
);
}
else
{
graph.getSolution();
}
//
system("pause");
}
上面的代码能处理自环的情况，可面临一个链上套了很多环的情况就会TLE，test 13应该就是这样的一个case。
