SGU 101 — Domino
一道极其经典的欧拉路径问题.
做法可以见这里:
http://www.briefdream.com/sgu-101/
很详细了…
第一次写欧拉路径,写的还是比较恶心(自己瞎写的=.=).本来是1Y的,结果…把No solution写成了Impossible=.=…
本不想贴代码的,太恶心了…
{
SGU 101; Domino
- sqybi’s code
- Eular Path
}
//for my winsty
program sgu101_sqybi;
const
nn = 100;
tt = 6;
var
n, i, s, st, l: longint;
a: array[0..1, 1..nn]of longint;
q: array[1..nn]of longint;
head, d: array[0..tt]of longint;
v: array[1..nn]of boolean;
next, adj: array[-nn..nn]of longint;
procedure addEdge(x, y: longint);
begin
adj[i] := y;
next[i] := head[x];
head[x] := i;
adj[-i] := x;
next[-i] := head[y];
head[y] := -i;
inc(d[x]);
inc(d[y]);
end;
procedure dfs(x: longint);
var
temp: longint;
begin
temp := head[x];
while temp <> 0 do begin
if not v[abs(temp)] then begin
v[abs(temp)] := true;
dfs(adj[temp]);
inc(l);
q[l] := temp;
end;
temp := next[temp];
end;
end;
begin
readln(n);
for i:=1 to n do begin
readln(a[0, i], a[1, i]);
addEdge(a[0, i], a[1, i]);
end;
s := 0;
st := 0;
for i:=0 to 6 do
if odd(d[i]) then begin
inc(s);
st := i;
end;
if s > 2 then begin
writeln(’No solution’);
halt;
end;
if s = 0 then
for i:=0 to 6 do
if d[i] <> 0 then
st := i;
fillchar(v, sizeof(v), false);
l := 0;
dfs(st);
if l < n then begin
writeln(’No solution’);
halt;
end;
for i:=l downto 1 do begin
write(abs(q[i]), ‘ ‘);
if q[i] > 0 then
writeln(’+')
else
writeln(’-');
end;
end.
阅读(131 次)