Cod sursa(job #1628074)

Utilizator DoubleNyNinicu Cristian DoubleNy Data 3 martie 2016 20:54:50
Problema Ciclu Eulerian Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 2.75 kb
type
     edge=record
      x,y:integer;
     end;
var
   edges:array[1..200] of edge;
   adiacenta:array[1..10000,1..10000] of integer;
   degree,lista:array[1..200005] of integer;
   i,j,m,n,noduri,muchii,neigh,u,grade:integer;

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

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


end;

procedure erase(a,b:integer);
var i,j:integer;
begin
     for i:=1 to muchii do
     if (edges[i].x=a) and (edges[i].y=b) then
     begin
          edges[i].x:=0;
          edges[i].y:=0;
          break;
     end;
     for j:=i to muchii do
     begin
          edges[j].x:=edges[j+1].x;
          edges[j].y:=edges[j+1].y;
     end;
     dec(muchii);
     fillchar(degree,sizeof(degree),0);
     for i:=1 to noduri do
    begin
        for j:=1 to muchii do
        if (edges[j].x=i) or (edges[j].y=i) then inc(degree[i]);
    end;
end;
procedure push(n:integer);

begin
    lista[u]:=n;
    inc(u);
end;

procedure Euler(nod:integer);
begin
    while (degree[nod]>0) do
    begin
        neigh:=next(nod);
        erase(nod,neigh);
        euler(neigh);
    end;
    push(nod);
end;
function dfs(n:integer):boolean;
var i,p,u,v:integer;
    Queue,Visited:array[1..200005] of longint;
begin
     fillchar(Visited,sizeof(Visited),0);
     p:=1;
     u:=1;
     queue[1]:=1; visited[1]:=1;
     while p<=u do
     begin
          v:=queue[p]; inc(p);
          for i:=1 to n do
          if (adiacenta[v,i]=1) and (visited[i]=0) then
          begin
             inc(u);
             queue[u]:=i;
             visited[i]:=1;
          end;

     end;
     dfs:=true;
     for i:=1 to n do
     if visited[i]=0 then dfs:=not(dfs);
end;


BEGIN
    assign(input,'ciuruleuler.in'); reset(input);
    assign(output,'ciclueuler.out'); rewrite(output);
    readln(input,noduri,muchii);
    for i:=1 to muchii do
    readln(input,edges[i].x,edges[i].y);
    fillchar(adiacenta,sizeof(adiacenta),0);
    for i:=1 to muchii do
    adiacenta[edges[i].x,edges[i].y]:=1;
    fillchar(degree,sizeof(degree),0);
    u:=1;
    fillchar(lista,sizeof(lista),0);
    for i:=1 to noduri do
    begin
        for j:=1 to muchii do
        if (edges[j].x=i) or (edges[j].y=i) then inc(degree[i]);
    end;
    grade:=0;
    for i:=1 to noduri do grade:=grade+degree[i];
    if not(dfs(1)) or (grade mod 2<>1) then
    begin
         write(output,'-1');
         exit;
    end;

    Euler(1);
    for i:=1 to u-2 do write(output,lista[i]);
    close(input);
    close(output);
END.