// Wyszukiwanie cykli i ścieżek Hamiltona
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program hamilton;

// Typy danych

type
  PSLel = ^SLel;          // Wskaźnik elementów listy
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

// Zmienne globalne

var
  m, n  : integer;              // Liczba krawędzi i wierzchołków
  graf : array of PSLel;     // Tablica list sąsiedztwa
  S    : array of integer;      // Tablica-stos
  sptr : integer;               // Wskaźnik stosu
  visited : array of boolean;   // Tablica odwiedzin

// Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
// v-wierzchołek bieżący
//--------------------------------------------------------------
procedure DFSHamilton (v : integer);
var
  i    : integer;
  test : boolean;
  p    : PSLel;
begin
  S [sptr] := v;              // Wierzchołek v na stos
  inc (sptr);
  if sptr < n then              // Jest ścieżka Hamiltona?
  begin
    visited [v] := true;      // Nie ma, odwiedzamy v
    p := graf [v];
    while p <> nil do           // Przeglądamy sąsiadów v
    begin
      if not visited [p^.v] then DFSHamilton (p^.v); // Wywołanie rekurencyjne
      p := p^.next;             // Następny sąsiad
    end;
    visited [v] := false;     // Wycofujemy się z v
  end
  else                          // Jest ścieżka Hamiltona
  begin
    test := false;              // Zakładamy brak cyklu
    p := graf [v];               // Przeglądamy sąsiadów
    while p <> nil do
    begin
      if p^.v = 0 then          // Jeśli sąsiadem jest wierzchołek 0, 
      begin
        test := true;           // to mamy cykl
        break;
      end;
      p := p^.next;             // Następny sąsiad
    end;
    if test then write ('Hamiltonian Cycle :')
    else         write ('Hamiltonian Path  :');
    for i := 0 to sptr-1 do   // Wypisujemy ścieżkę Hamiltona
      write (S [i] :3);
    if test then write (0:3); // Dla cyklu dopisujemy wierzchołek startowy
    writeln;
  end;
  dec (sptr);                 // Wierzchołek v usuwamy ze stosu
end;

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

var
  i, v1, v2 : integer;
  p, r     : PSLel;
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
    graf [i]    := nil;
    visited [i] := false;
  end;
  SetLength (S, n);
  sptr := 0;

  // Odczytujemy definicje krawędzi grafu

  for i := 0 to m-1 do
  begin
    read (v1, v2);
    new (p);
    p^.v := v2;
    p^.next := graf [v1];
    graf [v1] := p;
    new (p);
    p^.v := v1;
    p^.next := graf [v2];
    graf [v2] := p;
  end;

  writeln;

  // Wyświetlamy ścieżki i cykle Hamiltona

  DFSHamilton (0);

  // Usuwamy zmienne dynamiczne

  SetLength (visited, 0);
  SetLength (S, 0);

  for i := 0 to n-1 do
  begin
    p := graf [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;

  SetLength (graf, 0);
end.

// Wyszukiwanie cykli i ścieżek Hamiltona
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

struct SLel
{
  SLel * next;
  int v;
};

// Zmienne globalne

int m, n;                       // Liczba krawędzi i wierzchołków
SLel **graf;                 // Tablica list sąsiedztwa
int *S;                         // Tablica-stos
int sptr;                       // Wskaźnik stosu
bool *visited;                  // Tablica odwiedzin

// Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
// v-wierzchołek bieżący
//--------------------------------------------------------------
void DFSHamilton (int v)
{
  int i;
  bool test;
  SLel *p;

  S [sptr++] = v;             // Wierzchołek v na stos
  if(sptr < n)                // Jest ścieżka Hamiltona?
  {
    visited [v] = true;       // Nie ma, odwiedzamy v
    for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów v
      if(!visited [p->v]) DFSHamilton (p->v); // Wywołanie rekurencyjne
    visited [v] = false;      // Wycofujemy się z v
  }
  else                          // Jest ścieżka Hamiltona
  {
    test = false;               // Zakładamy brak cyklu
    for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów
      if(! (p->v))          // Jeśli sąsiadem jest wierzchołek 0, 
      {
        test = true;            // to mamy cykl
        break;
      }

    if(test) cout << "Hamiltonian Cycle :";
    else     cout << "Hamiltonian Path  :";

    for(i = 0; i < sptr; i++) // Wypisujemy ścieżkę Hamiltona
      cout << setw (3) << S [i];
    if(test) cout << setw (3) << 0; // Dla cyklu dopisujemy wierzchołek startowy
    cout << endl;
  }
  sptr--;                       // Wierzchołek v usuwamy ze stosu
}

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

int main()
{
  int i, v1, v2;
  SLel *p, *r;

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

  // Tworzymy tablice dynamiczne

  graf    = new SLel * [n];
  visited = new bool [n];
  for(i = 0; i < n; i++)
  {
    graf [i]    = NULL;
    visited [i] = false;
  }
  S = new int [n];
  sptr = 0;

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    p = new SLel;
    p->v = v2;
    p->next = graf [v1];
    graf [v1] = p;
    p = new SLel;
    p->v = v1;
    p->next = graf [v2];
    graf [v2] = p;
  }

  cout << endl;

  // Wyświetlamy ścieżki i cykle Hamiltona

  DFSHamilton (0);

  // Usuwamy zmienne dynamiczne

  delete [] visited;
  delete [] S;

  for(i = 0; i < n; i++)
  {
    p = graf [i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] graf;

  return 0;}

' Wyszukiwanie cykli i ścieżek Hamiltona
' Data: 10.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy danych

Type SLel
  Next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer m, n     ' Liczba krawędzi i wierzchołków
Dim Shared As SLel Ptr Ptr graf ' Tablica list sąsiedztwa
Dim Shared As Integer Ptr S    ' Tablica-stos
Dim Shared As Integer sptr     ' Wskaźnik stosu
Dim Shared As Byte Ptr visited ' Tablica odwiedzin

' Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
' v-wierzchołek bieżący
'--------------------------------------------------------------
Sub DFSHamilton (ByVal v As Integer)

  Dim As Integer i, test
  Dim As SLel Ptr p

  S [sptr] = v          ' Wierzchołek v na stos
  sptr += 1
  If sptr < n Then        ' Jest ścieżka Hamiltona?
    visited [v] = 1     ' Nie ma, odwiedzamy v
    p = graf [v]
    While p               ' Przeglądamy sąsiadów v
      If visited [p->v] = 0 Then DFSHamilton (p->v) ' Wywołanie rekurencyjne
      p = p->Next         ' Następny sąsiad
    Wend
    visited [v] = 0     ' Wycofujemy się z v
  Else                    ' Jest ścieżka Hamiltona
    test = 0              ' Zakładamy brak cyklu
    p = graf [v]
    While p               ' Przeglądamy sąsiadów
      If p->v = 0 Then    ' Jeśli sąsiadem jest wierzchołek 0, 
        test = 1          ' to mamy cykl
        Exit While
      End If
      p = p->Next         ' Następny sąsiad
    Wend
   
    If test = 1 then
    	Print "Hamiltonian Cycle :";
    Else
      Print "Hamiltonian Path  :";
    End If
   
    For i = 0 To sptr-1 ' Wypisujemy ścieżkę Hamiltona
      Print Using "###";S [i];
    Next
   
    If test = 1 Then Print Using "###";0; ' Dla cyklu dopisujemy wierzchołek startowy
    Print
  End if
  sptr -= 1               ' Wierzchołek v usuwamy ze stosu
End Sub

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

Dim As Integer i, v1, v2
Dim As SLel Ptr p, r

Open Cons For Input As #1

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

' Tworzymy tablice dynamiczne

graf    = New SLel Ptr [n]
visited = New Byte [n]
For i = 0 To n-1
  graf [i]    = 0
  visited [i] = 0
Next
S = New Integer [n]
sptr = 0

' Odczytujemy definicje krawędzi grafu

For i = 0 To m-1
  Input #1, v1, v2
  p = New SLel
  p->v = v2
  p->next = graf [v1]
  graf [v1] = p
  p = New SLel
  p->v = v1
  p->next = graf [v2]
  graf [v2] = p
Next

Print

' Wyświetlamy ścieżki i cykle Hamiltona

DFSHamilton (0)

' Usuwamy zmienne dynamiczne

Delete [] visited
Delete [] S

For i = 0 To n-1
  p = graf [i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf

End