Cod sursa(job #1631982)

Utilizator DoubleNyNinicu Cristian DoubleNy Data 5 martie 2016 20:39:34
Problema Ciclu Eulerian Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 2 kb
const
    maxN=100002;
    maxE=500002;
type ed=record
     x,y:longint;
     end;
var raspuns:array[1..MaxE] of longint;
    edges,nodes,i,j,u:longint;
    edge:array[1..MaxE] of ed;
    degree:array[1..MaxN] of longint;

function eulerian:boolean;
begin
    i:=1;
    while (i<=nodes) and not(odd(degree[i])) and (degree[i]<>0) do inc(i);
    if i>nodes then eulerian:=true
    else eulerian:=false;
end;

procedure eulerfind(node:longint);
var neigh:longint;

function next(x:integer):integer;
var i,j:integer;
begin
     for i:=1 to edges do
     if edge[i].x=x then
     begin
          next:=edge[i].y;
          exit;
     end;

     for i:=1 to edges do
     if edge[i].y=x then
     begin
          next:=edge[i].x;
          exit;
     end;


end;

procedure erase(a,b:integer);
var i,j:integer;
begin
     dec(degree[a]);
     dec(degree[b]);
     for i:=1 to edges do
     if (edge[i].x=a) and (edge[i].y=b) then
     begin
          edge[i].x:=0;
          edge[i].y:=0;
          break;
     end;
     for j:=i to edges do
     begin
          edge[j].x:=edge[j+1].x;
          edge[j].y:=edge[j+1].y;
     end;
     dec(edges);
end;

begin
     while degree[node]>0 do
     begin
         neigh:=next(node);
         erase(node,neigh);
         eulerfind(neigh);
     end;
     inc(u);
     raspuns[u]:=node;
end;

Begin
     assign(input,'ciclueuler.in'); reset(input);
     assign(output,'ciclueuler.out'); rewrite(output);
     fillchar(degree,sizeof(degree),0);
     readln(input,nodes,edges);
     for i:=1 to edges do
     begin
        readln(input,edge[i].x,edge[i].y);
        if edge[i].x<>edge[i].y then begin inc(degree[edge[i].x]); inc(degree[edge[i].y]); end;
     end;
     //verificare
      if not(eulerian) then
      begin
          write('-1');
          exit;
      end;
     //verificare
     u:=0;
     EulerFind(1);
     for i:=2 to u do write(output,raspuns[i],' ');
     close(input);
     close(output);
End.