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

program hamilton;

// Typy danych

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

// Zmienne globalne

var
  m, n  : integer;              // Liczba krawędzi i wierzchołków
  graf : array of PslistEl;     // 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    : PslistEl;
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     : PslistEl;
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 slistEl
{
  slistEl * next;
  int v;
};

// Zmienne globalne

int m, n;                       // Liczba krawędzi i wierzchołków
slistEl **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;
  slistEl *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;
  slistEl *p, *r;

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

  // Tworzymy tablice dynamiczne

  graf    = new slistEl * [ 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 slistEl;
    p->v = v2;
    p->next = graf [ v1 ];
    graf [ v1 ] = p;
    p = new slistEl;
    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 slistEl
  Next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer m, n     ' Liczba krawędzi i wierzchołków
Dim Shared As slistEl 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 slistEl 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 slistEl 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 slistEl 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 slistEl
  p->v = v2
  p->next = graf [ v1 ] 
  graf [ v1 ] = p
  p = New slistEl
  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