[题目来源]：《全国青少年信息学奥林匹克联赛培训教材》（粉书）
[关键字]：欧拉路径（回路）
[题目大意]：给出一个图G问，是否存在一条欧拉路径（回路），若有则输出字典序最小的解。
//============================================================================================================
[分析]：1、如果图中奇数度的点只有0或2个则存在，0时从任意点有一条回路，2是从任意奇数度的点有一条以另一个奇数度的点为汇点的路径。2、求欧拉路径时递规求解，倒着记录路径。
[代码]：
View Code 1 program project1; 2 var 3 a: array[0..100,0..100] of longint; 4 p: array[0..200] of longint; 5 r: array[0..100] of longint; 6 now, n: longint; 7 8 procedure init; 9 var10 i, j: longint;11 begin12 readln(n);13 for i := 1 to n do14 for j := 1 to n do15 begin16 read(a[i,j]);17 if a[i,j] = 1 then18 begin19 inc(r[i]);20 inc(r[j]);21 end;22 end;23 for i := 1 to n do r[i] := r[i] div 2;24 end;25 26 procedure dfs(k: longint);27 var28 i: longint;29 begin30 for i := 1 to n do31 if a[k,i] = 1 then32 begin33 a[k,i] := 0;34 a[i,k] := 0;35 dfs(i);36 end;37 inc(now);38 p[now] := k;39 end;40 41 procedure work;42 var43 i, temp, st: longint;44 begin45 temp := 0;46 for i := n downto 1 do47 if odd(r[i]) then begin inc(temp); st := i; end;48 //writeln(temp,' ',st);49 if not ((temp = 0) or (temp = 2)) then begin writeln('NO'); exit; end;50 now := 0;51 if temp = 0 then dfs(1) else dfs(st);52 write(p[now]);53 for i := now-1 downto 1 do write('->',p[i]);54 end;55 56 begin57 assign(input,'d:\in.txt');reset(input);58 assign(output,'d:\out.txt');rewrite(output);59 init;60 work;61 close(input);62 close(output);63 end.转载于:https://www.cnblogs.com/procedure2012/archive/2011/10/27/2226290.html
