Cod sursa(job #1537061)

Utilizator ili226Vlad Ilie ili226 Data 26 noiembrie 2015 21:38:00
Problema Ciclu Eulerian Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 1.42 kb
type nd=^nod;
     nod=record
          val:longint;
          exista:boolean;
          next:nd
         end;
     graf=array[1..100000]of nd;
var f:text;
    g:graf;
    m,n,i,x,y,k:longint;
    p:nd;
    ii_bun:boolean;
    ma:array[1..100000,1..100000]of word;
    ver:array[1..100000]of boolean;
    ciclu:array[1..500000]of longint;
procedure adauga(var g:graf;x,y:longint);
var p:nd;
begin
 new(p);
 ver[x]:=not(ver[x]);
 p^.val:=y;
 p^.exista:=true;
 p^.next:=g[x];
 g[x]:=p
end;
procedure df(x:longint);
var p:nd;
begin
ver[x]:=false;
p:=g[x];
while p<>nil do
 begin
  if ver[p^.val] then
   df(p^.val);
  p:=p^.next
 end
end;
procedure euler(x:longint);
var i:longint;
begin
for i:=1 to n do
 if ma[x,i]>0 then
  begin
   dec(ma[x,i]);
   {if i<>x then }dec(ma[i,x]);
   euler(i)
  end;
inc(k);
ciclu[k]:=x
end;

begin
assign(f,'ciclueuler.in');
reset(f);
readln(f,n,m);
for i:=1 to n do
 ver[i]:=true;
ii_bun:=true;
for i:=1 to m do
 begin
  readln(f,x,y);
  adauga(g,x,y);
  adauga(g,y,x);
  inc(ma[x,y]);
  inc(ma[y,x]);
 end;
close(f);
for i:=1 to n do
 if not(ver[i])then ii_bun:=false;
if ii_bun then
 begin
  df(1);
  for i:=1 to n do
   if ver[i] then ii_bun:=false;
 end;
assign(f,'ciclueuler.out');
rewrite(f);
if ii_bun then
 begin
  k:=0;
  euler(1);
  for i:=1 to k do
   write(f,ciclu[i],' ')
 end
          else
 writeln(f,'-1');
close(f);
end.