// Wyszukiwanie cyklu Eulera
// Data: 19.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program EulerCycle;

// Typy dla dynamicznej macierzy sąsiedztwa
type
  nptr = array of integer;   // Wiersz

// Zmienne globalne
var
  n, m, sptr : integer;
  A   : array of nptr;       // Macierz sąsiedztwa
  S   : array of integer;    // Stos w tablicy

// Procedura wyszukuje cykl Eulera
// We:
// v-wierzchołek startowy
//--------------------------------
procedure DFSEuler (v : integer);
var
  i : integer;
begin
  for i := 0 to n-1 do     // Przeglądamy sąsiadów
    while A [v][i] > 0 do
    begin
      dec (A [v][i]);  // Usuwamy krawędź
      dec (A [i][v]);
      DFSEuler (i);        // Rekurencja
    end;
  S [sptr] := v;           // Wierzchołek v umieszczamy na stosie
  inc (sptr);
end;

// **********************
// *** Program główny ***
// **********************

var
  i, j, v1, v2 : integer;
begin
  read (n, m);              // Czytamy liczbę wierzchołków i krawędzi

  SetLength (A, n);         // Tworzymy tablicę wskaźników
  SetLength (S, m+1);       // Tworzymy stos
  sptr := 0;

  for i := 0 to n-1 do
    SetLength (A [i], n); // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for i := 0 to n-1 do
    for j := 0 to n-1 do A [i][j] := 0;

  // Odczytujemy kolejne definicje krawędzi

  for i := 1 to m do
  begin
    read (v1, v2);        // wierzchołki końcowe krawędzi
    inc (A [v1][v2]); // Krawędź v1->v2 obecna
    inc (A [v2][v1]); // Krawędź v2->v1 obecna
  end;

  writeln;

  // Wyznaczamy cykl Eulera

  DFSEuler (0);

  // Wypisujemy zawartość stosu

  write ('EULERIAN CYCLE : ');

  for i := 0 to sptr-1 do write (S [i], ' ');
  writeln;

  // Usuwamy tablice dynamiczne

  for i := 0 to n-1 do SetLength (A [i], 0);
  SetLength (A, 0);
  SetLength (S, 0);
end.

// Wyszukiwanie cyklu Eulera
// Data: 19.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Zmienne globalne

int n, m, sptr;
int ** A;                    // Macierz sąsiedztwa
int * S;                     // Stos w tablicy

// Procedura wyszukuje cykl Eulera
// We:
// v-wierzchołek startowy
//--------------------------------
void DFSEuler (int v)
{
  int i;

  for(i = 0; i < n; i++)   // Przeglądamy sąsiadów
    while(A [v][i])
    {
      A [v][i] --;       // Usuwamy krawędź
      A [i][v] --;
      DFSEuler (i);        // Rekurencja
    }
  S [sptr++] = v;          // Wierzchołek v umieszczamy na stosie
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i, j, v1, v2;

  cin >> n >> m;             // Czytamy liczbę wierzchołków i krawędzi

  A = new int * [n];       // Tworzymy tablicę wskaźników
  S = new int [m+1];     // Tworzymy stos
  sptr = 0;

  for(i = 0; i < n; i++)
    A [i] = new int [n]; // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) A [i][j] = 0;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;   // wierzchołki końcowe krawędzi
    A [v1][v2] ++; // Krawędź v1->v2 obecna
    A [v2][v1] ++; // Krawędź v2->v1 obecna
  }

  cout << endl;

  // Wyznaczamy cykl Eulera

  DFSEuler (0);

  // Wypisujemy zawartość stosu

  cout << "EULERIAN CYCLE : ";

  for(i = 0; i < sptr; i++) cout << S [i] << " ";
  cout << endl;

  // Usuwamy tablice dynamiczne

  for(i = 0; i < n; i++) delete [] A [i];

  delete [] A;
  delete [] S;

  return 0;}

' Wyszukiwanie cyklu Eulera
' Data: 19.03.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Zmienne globalne

Dim Shared As Integer n, m, sptr
Dim Shared As Integer Ptr Ptr A ' Macierz sąsiedztwa
Dim Shared As Integer Ptr S     ' Stos w tablicy

' Procedura wyszukuje cykl Eulera
' We:
' v-wierzchołek startowy
'--------------------------------
Sub DFSEuler (byval v As Integer)
 
  Dim As Integer i

  For i = 0 To n-1          ' Przeglądamy sąsiadów
    While A [v][i]
      A [v][i] -= 1       ' Usuwamy krawędź
      A [i][v] -= 1
      DFSEuler (i)          ' Rekurencja
    Wend
  Next
  S [sptr] = v              ' Wierzchołek v umieszczamy na stosie
  sptr += 1
End Sub

' **********************
' *** Program główny ***
' **********************

Dim As integer i, j, v1, v2

Open Cons For Input As #1

Input #1, n, m                ' Czytamy liczbę wierzchołków i krawędzi

A = New integer Ptr [n]     ' Tworzymy tablicę wskaźników
S = New Integer [m+1]     ' Tworzymy stos
sptr = 0

For i = 0 To n-1
  A [i] = New Integer [n] ' Tworzymy wiersze macierzy sąsiedztwa
Next

' Macierz wypełniamy zerami

For i = 0 To n-1
  For j = 0 To n-1
  	 A [i][j] = 0
  Next
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m-1
  Input #1, v1, v2     ' wierzchołki końcowe krawędzi
  A [v1][v2] += 1  ' Krawędź v1->v2 obecna
  A [v2][v1] += 1  ' Krawędź v2->v1 obecna
Next

Print

Close #1

' Wyznaczamy cykl Eulera

DFSEuler (0)

' Wypisujemy zawartość stosu

Print "EULERIAN CYCLE :";

For i = 0 To sptr-1
  Print S [i];
Next
Print

' Usuwamy tablice dynamiczne

For i = 0 To n-1
  Delete [] A [i]
Next

Delete [] A
Delete [] S

End

// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Fleury'ego
// Data: 8.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program fleury;

// Typy dla dynamicznej macierzy
type
  nptr = array of byte;  // Wiersz

// Zmienne globalne
var
  n, m, cv, sptr : integer;
  A   : array of nptr;        // Macierz sąsiedztwa
  S   : array of integer;     // Stos w tablicy
  D   : array of integer;     // Tablica numerów wierzchołków

// Funkcja wyszukująca mosty w grafie
// We:
// v -numer wierzchołka startowego
// vf-ojciec wierzchołka v na drzewie rozpinającym
// Wy:
// Parametr Low dla wierzchołka v
//---------------------------------------------------
function DFSb (v, vf : integer) : integer;
var
  Low, temp, i : integer;
begin
  D [v] := cv;              // Numerujemy wierzchołek
  Low  := cv;                 // Wstępna wartość Low
  inc (cv);                 // Numer dla następnego wierzchołka
  for i := 0 to n-1 do      // Przeglądamy sąsiadów v
    if(A [v][i] > 0) and (i <> vf) then
    begin
      if D [i] = 0 then     // Jeśli sąsiad nieodwiedzony, to
      begin
        temp :=DFSb (i, v); // to wywołujemy rekurencyjnie DFSb()
        if temp < Low then Low := temp; // Modyfikujemy Low
      end
      else if D [i] < Low then Low := D [i];
    end;

  if(vf > -1) and (Low = D [v]) then // Mamy most?
  begin
    A [vf][v] := 2;       // Oznaczamy krawędź vf-v jako most
    A [v][vf] := 2;
  end;

  DFSb := Low;
end;

// Procedura wyszukuje cykl lub ścieżkę Eulera
// We:
// v-wierzchołek startowy
//--------------------------------------------
procedure findEuler (v : integer);
var
  u, w, i : integer;
begin
  while true do               // W pętli przetwarzamy graf
  begin
    S [sptr] := v;          // v umieszczamy na stosie
    inc (sptr);

    u := 0;                   // Szukamy pierwszego sąsiada v
    while(u < n) and (A [v][u] = 0) do inc (u);

    if u = n then break;      // Nie ma sąsiadów, kończymy

    for i := 0 to n-1 do D [i] := 0; // Zerujemy tablicę D

    cv := 1;                  // Numer pierwszego wierzchołka dla DFS
    DFSb (v, -1);           // Identyfikujemy krawędzie-mosty

    // Szukamy krawędzi nie będącej mostem

    w := u+1;
    while(A [v][u] = 2) and (w < n) do
    begin
      if A [v][w] > 0 then u := w;
      inc (w);
    end;

    A [v][u] := 0;        // Usuwamy krawędź v-u
    A [u][v] := 0;
    v := u;                   // Przechodzimy do u
  end;
end;

// **********************
// *** Program główny ***
// **********************

var
  i, j, v1, v2 : integer;
  VD : array of integer;      // Stopnie wierzchołków
begin
  read (n, m);              // Czytamy liczbę wierzchołków i krawędzi

  SetLength (A, n);         // Tworzymy tablicę wskaźników
  for i := 0 to n-1 do
    SetLength (A [i], n); // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for i := 0 to n-1 do
    for j := 0 to n-1 do A [i][j] := 0;

  SetLength (VD, n);              // Tworzymy tablicę stopni
  for i := 0 to n-1 do  // Zerujemy tablicę stopni
    VD [i] := 0;

  SetLength (D, n);     // Tworzymy tablicę numerów

  SetLength (S, m+1);   // Tworzymy pusty stos
  sptr := 0;

  // Odczytujemy kolejne definicje krawędzi

  for i := 1 to m do
  begin
    read (v1, v2);      // Wierzchołek startowy i końcowy krawędzi
    A [v1][v2] := 1;  // Krawędź v1->v2 obecna
    A [v2][v1] := 1;  // Krawędź v2->v1 obecna
    inc (VD [v1]);
    inc (VD [v2]);    // Obliczamy stopnie v1 i v2
  end;

  writeln;

  // Szukamy pozycji startowej v1

  for v1 := 0 to n-1 do
    if VD [v1] > 0 then break;

  for i := v1 to n-1 do
    if VD [i] mod 2 = 1 then
    begin
      v1 := i;
      break;
    end;

  // Wyznaczamy cykl lub ścieżkę Eulera

  findEuler (v1);

  // Wypisujemy zawartość stosu

  if VD [v1] mod 2 = 1 then write ('EULERIAN PATH :') else write ('EULERIAN CYCLE :');
 
  for i := 0 to sptr-1 do write (S [i] :3);
  writeln;

  // Usuwamy tablice dynamiczne

  for i := 0 to n-1 do SetLength (A [i], 0);
  SetLength (A, 0);
  SetLength (S, 0);
  SetLength (D, 0);
  SetLength (VD, 0);
end.

// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Fleury'ego
// Data: 8.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Zmienne globalne

int n, m, cv, sptr;
char **A; // Macierz sąsiedztwa
int *S;   // Stos w tablicy
int *D;   // Tablica numerów wierzchołków

// Funkcja wyszukująca mosty w grafie
// We:
// v -numer wierzchołka startowego
// vf-ojciec wierzchołka v na drzewie rozpinającym
// Wy:
// Parametr Low dla wierzchołka v
//---------------------------------------------------
int DFSb (int v, int vf)
{
  int Low, temp, i;

  D [v] = cv;            // Numerujemy wierzchołek
  Low  = cv;               // Wstępna wartość Low
  cv++;                    // Numer dla następnego wierzchołka
  for(i = 0; i < n; i++) // Przeglądamy sąsiadów v
    if(A [v][i] && (i != vf))
    {
      if(!D [i])          // Jeśli sąsiad nieodwiedzony, to
      {
        temp = DFSb (i, v); // to wywołujemy rekurencyjnie DFSb()
        if(temp < Low) Low = temp; // Modyfikujemy Low
      }
      else if(D [i] < Low) Low = D [i];
    }

  if((vf > -1) && (Low == D [v])) // Mamy most?
    A [vf][v] = A [v][vf] = 2; // Oznaczamy krawędź vf-v jako most

  return Low;
}

// Procedura wyszukuje cykl lub ścieżkę Eulera
// We:
// v-wierzchołek startowy
//--------------------------------------------
void findEuler (int v)
{
  int u, w, i;

  while(true)         // W pętli przetwarzamy graf
  {
    S [sptr++] = v;   // v umieszczamy na stosie

    for(u = 0; (u < n) && !A [v][u];u++); // Szukamy pierwszego sąsiada v

    if(u == n) break; // Nie ma sąsiadów, kończymy

    for(i = 0; i < n; i++) D [i] = 0; // Zerujemy tablicę D

    cv = 1;             // Numer pierwszego wierzchołka dla DFS
    DFSb (v, -1);     // Identyfikujemy krawędzie-mosty

    // Szukamy krawędzi nie będącej mostem

    for(w = u+1; (A [v][u] == 2) && (w < n); w++)
      if(A [v][w]) u = w;

    A [v][u] = A [u][v] = 0; // Usuwamy krawędź v-u
    v = u;              // Przechodzimy do u
  }
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i, j, v1, v2;
  int *VD;                    // Stopnie wierzchołków

  cin >> n >> m;              // Czytamy liczbę wierzchołków i krawędzi

  A = new char * [n];       // Tworzymy tablicę wskaźników
  for(i = 0; i < n; i++)
    A [i] = new char [n]; // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) A [i][j] = 0;

  VD = new int [n];      // Tworzymy tablicę stopni
  for(i = 0; i < n; i++) // Zerujemy tablicę stopni
    VD [i] = 0;

  D = new int [n];     // Tworzymy tablicę numerów

  S = new int [m+1]; // Tworzymy pusty stos
  sptr = 0;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    A [v1][v2] = 1; // Krawędź v1->v2 obecna
    A [v2][v1] = 1; // Krawędź v2->v1 obecna
    VD [v1] ++;
    VD [v2] ++;       // Obliczamy stopnie v1 i v2
  }

  cout << endl;

  // Szukamy pozycji startowej v1

  for(v1 = 0; v1 < n; v1++)
    if(VD [v1]) break;

  for(i = v1; i < n; i++)
    if(VD [i] % 2)
    {
      v1 = i;
      break;
    }

  // Wyznaczamy cykl lub ścieżkę Eulera

  findEuler (v1);

  // Wypisujemy zawartość stosu

  if(VD [v1] % 2) cout << "EULERIAN PATH :"; else cout << "EULERIAN CYCLE :";

  for(i = 0; i < sptr; i++) cout << setw (3) << S [i];
  cout << endl;

  // Usuwamy tablice dynamiczne

  for(i = 0; i < n; i++) delete [] A [i];
  delete [] A;
  delete [] S;
  delete [] D;
  delete [] VD;

  return 0;}

' Wyszukiwanie cyklu lub ścieżki Eulera
' Algorytm Fleury'ego
' Data: 8.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Zmienne globalne

Dim Shared As Integer n, m, cv, sptr
Dim Shared As Byte Ptr Ptr  A ' Macierz sąsiedztwa
Dim Shared As Integer Ptr S   ' Stos w tablicy
Dim Shared As Integer Ptr D   ' Tablica numerów wierzchołków

' Funkcja wyszukująca mosty w grafie
' We:
' v -numer wierzchołka startowego
' vf-ojciec wierzchołka v na drzewie rozpinającym
' Wy:
' Parametr Low dla wierzchołka v
'---------------------------------------------------
function DFSb (ByVal v As integer, ByVal vf As integer) As Integer

  Dim As Integer Low, temp, i

  D [v] = cv               ' Numerujemy wierzchołek
  Low  = cv                  ' Wstępna wartość Low
  cv += 1                    ' Numer dla następnego wierzchołka
  For i = 0 To n-1         ' Przeglądamy sąsiadów v
    if(A [v][i] > 0) AndAlso (i <> vf) Then
      If D [i] = 0 Then    ' Jeśli sąsiad nieodwiedzony, to
        temp = DFSb (i, v) ' to wywołujemy rekurencyjnie DFSb()
        If temp < Low Then Low = temp ' Modyfikujemy Low
      Else
        If D [i] < Low Then Low = D [i]
      End If
    End If
  Next
 
  if(vf > -1) AndAlso (Low = D [v]) Then ' Mamy most?
    A [vf][v] = 2: A [v][vf] = 2  ' Oznaczamy krawędź vf-v jako most
  End If
 
  Return Low
End Function

' Procedura wyszukuje cykl lub ścieżkę Eulera
' We:
' v-wierzchołek startowy
'--------------------------------------------
Sub findEuler (ByVal v As integer)

  Dim As Integer u, w, i

  While 1                    ' W pętli przetwarzamy graf
    S [sptr] = v           ' v umieszczamy na stosie
    sptr += 1

    u = 0
    while(u < n) AndAlso (A [v][u] = 0) ' Szukamy pierwszego sąsiada v
      u += 1
    Wend
   
    If u = n Then Exit While ' Nie ma sąsiadów, kończymy

    For i = 0 To n-1
      D [i] = 0            ' Zerujemy tablicę D
    Next

    cv = 1                   ' Numer pierwszego wierzchołka dla DFS
    DFSb (v, -1)           ' Identyfikujemy krawędzie-mosty

    ' Szukamy krawędzi nie będącej mostem

    w = u+1
    while(A [v][u] = 2) AndAlso (w < n)
      If A [v][w] > 0 Then u = w
      w += 1
    Wend
   
    A [v][u] = 0: A [u][v] = 0    ' Usuwamy krawędź v-u
    v = u                  ' Przechodzimy do u
  Wend
End Sub

' **********************
' *** Program główny ***
' **********************

Dim As Integer i, j, v1, v2
Dim As Integer Ptr VD      ' Stopnie wierzchołków

Open Cons For Input As #1

Input #1, n, m             ' Czytamy liczbę wierzchołków i krawędzi

A = New Byte Ptr [n]     ' Tworzymy tablicę wskaźników
For i = 0 To n-1
  A [i] = New Byte [n] ' Tworzymy wiersze macierzy sąsiedztwa
Next

' Macierz wypełniamy zerami

For i = 0 To n-1
  For j = 0 To n-1
  	 A [i][j] = 0
  Next
Next

VD = New integer [n]    ' Tworzymy tablicę stopni
For i = 0 To n-1        ' Zerujemy tablicę stopni
  VD [i] = 0
Next

D = New integer [n]     ' Tworzymy tablicę numerów

S = New integer [m+1] ' Tworzymy pusty stos
sptr = 0

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m-1
  Input #1, v1, v2   ' Wierzchołek startowy i końcowy krawędzi
  A [v1][v2] = 1 ' Krawędź v1->v2 obecna
  A [v2][v1] = 1 ' Krawędź v2->v1 obecna
  VD [v1] += 1
  VD [v2] += 1     ' Obliczamy stopnie v1 i v2
Next

Close #1

Print

' Szukamy pozycji startowej v1

v1 = 0
While v1 < n
  If VD [v1] > 0 Then Exit While
  v1 += 1
Wend

For i = v1 To n-1
  If VD [i] Mod 2 = 1 Then
    v1 = i
    Exit For
  End If
Next

' Wyznaczamy cykl lub ścieżkę Eulera

findEuler (v1)

' Wypisujemy zawartość stosu

If VD [v1] Mod 2 = 1 Then
  Print "EULERIAN PATH :";
Else
  Print "EULERIAN CYCLE :";
End If

For i = 0 To sptr-1
  Print Using "###";S [i];
Next
Print

' Usuwamy tablice dynamiczne

For i = 0 To n-1
  Delete [] A [i]
Next

Delete [] A
Delete [] S
Delete [] D
Delete [] VD

End

// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Hierholzera
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program hierholzer;

// Typy danych

type
  nptr = array of byte; // wiersz macierzy sąsiedztwa

  PDLel = ^DLel;  // Wskaźnik elementów listy dwukierunkowej
  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    v     : integer;
  end;

// Zmienne globalne

var
  m, n : integer;             // Liczba krawędzi i wierzchołków
  graf: array of nptr;        // Dynamiczna macierz sąsiedztwa
  visited : array of boolean; // Tablica odwiedzin

// Procedury obsługi listy dwukierunkowej
//---------------------------------------

// Procedura dołącza do listy nowy element
// za elementem wskazywanym przez p
//------------------------------------------
procedure addC (x : integer; p : PDLel);
var
  r : PDLel;
begin
  new (r);
  r^.v := x;
  r^.next := p^.next;
  if r^.next <> nil then r^.next^.prev := r;
  r^.prev := p;
  p^.next := r;
end;

// Procedura usuwa z listy element wskazywany przez p
//---------------------------------------------------
procedure remC (p : PDLel);
begin
  if p^.next <> nil then p^.next^.prev := p^.prev;
  if p^.prev <> nil then p^.prev^.next := p^.next;
  dispose (p);
end;

// Rekurencyjna funkcja dodająca do listy nowy cykl
// v-wierzchołek startowy i końcowy cyklu
// w-wierzchołek bieżący
// p-referencja do wskazania punktu wstawiania na liście
//--------------------------------------------------------
function DFSaddCycle (v, w : integer; var p : PDLel) : boolean;
var
  u : integer;
begin
  visited [w] := true;   // Oznaczamy v jako odwiedzony
  addC (w, p);           // Dodajemy w do cyklu
  p := p^.next;            // p wskazuje dodany element
  for u := 0 to n-1 do   // Przeglądamy sąsiadów w
    if graf [w][u] = 1 then
    begin
      if u = v then        // Cykl znaleziony?
      begin
        addC (v, p);     // Zamykamy cykl na liście C
        repeat
          graf [p^.v][p^.next^.v] := 0; // Usuwamy krawędzie cyklu
          if p^.v = v then Exit (true);
          p := p^.prev;
        until false;
      end;
      if not visited [u] and DFSaddCycle (v, u, p) then Exit (true);
    end;
  p := p^.prev;            // Z listy usuwamy w
  remC (p^.next);
  DFSaddCycle := false;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i, j, v1, v2 : integer;
  C   : PDLel;          // Lista cyklu Eulera
  p : PDLel;
begin
  read (n, m);           // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  SetLength (graf, n);
  SetLength (visited, n);
  for i := 0 to n-1 do
  begin
    SetLength (graf [i], n);
    for j := 0 to n-1 do graf [i][j] := 0;
  end;

  // Odczytujemy definicje krawędzi grafu

  for i := 0 to m-1 do
  begin
    read (v1, v2);
    graf [v1][v2] := 1;
  end;

  new (c);                   // Tworzymy listę z wierzchołkiem v1
  C^.v := v1;
  C^.next := nil;
  C^.prev := nil;

  p := C;                  // p wskazuje pierwszy element listy
  while p <> nil do        // Przeglądamy listę C
  begin
    for i := 0 to n-1 do // Szukamy sąsiadów
      if graf [p^.v][i] = 1 then
      begin
        for j := 0 to n-1 do visited [j] := false;
        DFSaddCycle (p^.v, i, p); // Dla każdego sąsiada uruchamiamy szukanie cyklu
      end;
    p := p^.next;          // Następny element listy C
  end;

  writeln;

  // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

  p := C;
  while p <> nil do
  begin
    write (p^.v:3);
    p := p^.next;
  end;

  writeln;

  // Usuwamy zmienne dynamiczne

  p := C;
  while p <> nil do
  begin
    p := C^.next;
    remC (c);
    C := p;
  end;

  for i := 0 to n-1 do SetLength (graf [i], 0);

  SetLength (graf, 0);
  SetLength (visited, 0);
end.

// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Hierholzera
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

struct DLel
{
  DLel *next, *prev;
  int v;
};

// Zmienne globalne

int m, n;       // Liczba krawędzi i wierzchołków
char **graf;    // Dynamiczna macierz sąsiedztwa
bool * visited; // Tablica odwiedzin

// Procedury obsługi listy dwukierunkowej
//---------------------------------------

// Procedura dołącza do listy nowy element
// za elementem wskazywanym przez p
//------------------------------------------
void addC (int x, DLel *p)
{
  DLel * r;

  r = new DLel;
  r->v = x;
  r->next = p->next;
  if(r->next) r->next->prev = r;
  r->prev = p;
  p->next = r;
}

// Procedura usuwa z listy element wskazywany przez p
//---------------------------------------------------
void remC (DLel *p)
{
  if(p->next) p->next->prev = p->prev;
  if(p->prev) p->prev->next = p->next;
  delete p;
}

// Rekurencyjna funkcja dodająca do listy nowy cykl
// v-wierzchołek startowy i końcowy cyklu
// w-wierzchołek bieżący
// p-referencja do wskazania punktu wstawiania na liście
//--------------------------------------------------------
bool DFSaddCycle (int v, int w, DLel * & p)
{
  int u;

  visited [w] = true;    // Oznaczamy v jako odwiedzony
  addC (w, p);           // Dodajemy w do cyklu
  p = p->next;             // p wskazuje dodany element
  for(u = 0; u < n; u++) // Przeglądamy sąsiadów w
    if(graf [w][u])
    {
      if(u == v)         // Cykl znaleziony?
      {
        addC (v, p);     // Zamykamy cykl na liście C
        do
        {
          graf [p->v][p->next->v] = 0; // Usuwamy krawędzie cyklu
          if(p->v == v) return true;
          p = p->prev;
        } while(true);
      }
      if(!visited [u] && DFSaddCycle (v, u, p)) return true;
    }
  p = p->prev;             // Z listy usuwamy w
  remC (p->next);
  return false;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i, j, v1, v2;
  DLel *C, *p;

  cin >> n >> m;                // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  graf    = new char * [n];
  visited = new bool [n];
  for(i = 0; i < n; i++)
  {
    graf [i] = new char [n];
    for(j = 0; j < n; j++) graf [i][j] = 0;
  }

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    graf [v1][v2] = 1;
  }

  C = new DLel;              // Tworzymy listę z wierzchołkiem v1
  C->v = v1;
  C->next = NULL;
  C->prev = NULL;

  for(p = C; p; p = p->next)  // Przeglądamy listę C
    for(i = 0; i < n; i++)    // Szukamy sąsiadów
      if(graf [p->v][i])
      {
        for(j = 0; j < n; j++) visited [j] = false;
        DFSaddCycle (p->v, i, p); // Dla każdego sąsiada uruchamiamy szukanie cyklu
      }

  cout << endl;

  // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

  for(p = C; p; p = p->next) cout << setw (3) << p->v;

  cout << endl;

  // Usuwamy zmienne dynamiczne

  p = C;
  while(p)
  {
    p = C->next;
    remC (c);
    C = p;
  }

  for(i = 0; i < n; i++) delete [] graf [i];

  delete [] graf;
  delete [] visited;

  return 0;}

' Wyszukiwanie cyklu lub ścieżki Eulera
' Algorytm Hierholzera
' Data: 10.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych

Type DLel
  Next As DLel Ptr
  prev As DLel Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer m, n      ' Liczba krawędzi i wierzchołków
Dim Shared As Byte Ptr Ptr graf ' Dynamiczna macierz sąsiedztwa
Dim Shared As Byte Ptr visited  ' Tablica odwiedzin

' Procedury obsługi listy dwukierunkowej
'---------------------------------------

' Procedura dołącza do listy nowy element
' za elementem wskazywanym przez p
'------------------------------------------
Sub addC (ByVal x As Integer, ByVal p As DLel Ptr)

  Dim As DLel Ptr r

  r = new DLel
  r->v = x
  r->next = p->Next
  If r->Next Then r->next->prev = r
  r->prev = p
  p->next = r
End Sub

' Procedura usuwa z listy element wskazywany przez p
'---------------------------------------------------
Sub remC (ByVal p As DLel Ptr)

  If p->Next Then p->next->prev = p->prev
  If p->prev Then p->prev->next = p->Next
  Delete p
End Sub

' Rekurencyjna funkcja dodająca do listy nowy cykl
' v-wierzchołek startowy i końcowy cyklu
' w-wierzchołek bieżący
' p-referencja do wskazania punktu wstawiania na liście
'--------------------------------------------------------
Function DFSaddCycle (ByVal v As integer, ByVal w As integer, ByRef p As DLel Ptr) As Integer

  Dim As Integer u

  visited [w] = 1   ' Oznaczamy v jako odwiedzony
  addC (w, p)       ' Dodajemy w do cyklu
  p = p->Next         ' p wskazuje dodany element
  For u = 0 To n-1  ' Przeglądamy sąsiadów w
    If graf [w][u] > 0 Then
      If u = v Then   ' Cykl znaleziony?
        addC (v, p) ' Zamykamy cykl na liście C
        Do
          graf [p->v][p->next->v] = 0 ' Usuwamy krawędzie cyklu
          If p->v = v then return 1
          p = p->prev
        loop While 1
      End If
      if(visited [u] = 0) AndAlso (DFSaddCycle (v, u, p) = 1) Then return 1
    End If
  Next
  p = p->prev        ' Z listy usuwamy w
  remC (p->next)
  return 0
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As integer i, j, v1, v2
Dim As DLel Ptr p, C

Open Cons For Input As #1

Input #1, n, m       ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy tablice dynamiczne

graf    = New Byte Ptr [n]
visited = New Byte [n]
For i = 0 To n-1
  graf [i] = New Byte [n]
  For j = 0 To n-1: graf [i][j] = 0: Next
Next

' Odczytujemy definicje krawędzi grafu

For i = 0 To m-1
  Input #1, v1, v2
  graf [v1][v2] = 1
Next

Close #1

C = New DLel      ' Tworzymy listę z wierzchołkiem v1
C->v = v1
C->next = 0
C->prev = 0

p = C
While p              ' Przeglądamy listę C
  For i = 0 To n-1 ' Szukamy sąsiadów
    If graf [p->v][i] = 1 Then
      For j = 0 To n-1: visited [j] = 0: Next
      DFSaddCycle (p->v, i, p) ' Dla każdego sąsiada uruchamiamy szukanie cyklu
    End If
  Next
  p = p->Next
Wend

Print

' Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

p = C
while p <> 0
  Print Using "###";p->v;
  p = p->Next
Wend

Print

' Usuwamy zmienne dynamiczne

p = C
While p
  p = C->Next
  remC (c)
  C = p
Wend

For i = 0 To n-1: Delete [] graf [i] : Next

Delete [] graf
Delete [] visited

End