Cài đặt thuật toán tìm chu trình Euler bằng Pascal

CÀI ĐẶT THUẬT TOÁN TÌM CHU TRÌNH EURLER BẰNG CHƯƠNG TRÌNH PASCAL
Chu trình Euler.
Chương trình tìm chu trình Euler.
Dữ liệu được lấy từ tệp EULER.INP là ma trận :

n
m

x1
y1

x2
y2

…
…

xm
ym

Trong đó, n số đỉnh, m là số cạnh


Sau khi lấy dữ liệu, chương trình sẽ xác định các có tồn tại chu trình Euler hay không, nếu có thì tìm chu trình và lưu vào tệp EULER.OUT có cấu trúc:

Dòng đầu : “NOSOLUTION” nếu không tồn tại chu trình Euler

Dòng đầu : “YES” nếu tồn tại chu trình Euler

 Dòng 2: z1,z2,…,zn,z1.

 Trong đó z1,z2,…,zn,z1 là chu trình.



Chương trình: (EULER.PAS)

program euler;
const max=30;
type mang=array[1..max] of integer;
var a:array[1..max,1..max] of integer;
c,tim:mang;
n,m,spt,k:integer;
f:text;
procedure input;
var i,x,y:integer;
begin
assign(f,`Euler.inp`);reset(f);
readln(f,n,m);
for i:=1 to m do
begin
readln(f,x,y);
a[x,y]:=1;
a[y,x]:=1;
end;
close(f);
end;
function kt:boolean;
var i,j,s,d:integer;
begin
d:=0;
for i:=1 to n do
begin
s:=0;
for j:=1 to n do
if(i<>j) then s:=s+a[i,j];
if s mod 2<>0 then inc(d);
end;
if d=0 then kt:=true
else kt:=false;
end;

procedure timp(var tim:mang;var spt:integer);
var x,u,v:integer;
begin
spt:=0;
c[1]:=1;u:=1;
repeat
v:=c[u];
x:=1;
while(x<=n) and (a[v,x]=0) do inc(x);
if a[v,x] <>0 then begin
inc(u);
c[u]:=x;
a[v,x]:=0;
a[x,v]:=0;
end
else
begin
inc(spt);
tim[spt]:=c[u];
dec(u);
end;
until u=0;
end;

BEGIN
input;
assign(f,`Euler.out`);rewrite(f);
if kt then begin
timp(tim,spt);
writeln(f,`YES`);
for k:=spt downto 2 do
write(f,tim[k],`-->`);
write(f,tim[1]);
end
else
write(f,`NO`);
close(f);
END.


File vào ví dụ: (EULER.INP)

4 5
1 2
3 4
File ra tương ứng: (EULER.OUT)

YES
1-->1-->2-->3-->4-->1