// 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;} 

Ly8gV3lzenVraXdhbmllIGN5a2xpIGkgxZtjaWXFvGVrIEhhbWlsdG9uYQovLyBEYXRhOiAxMC4wMi4yMDE0Ci8vIChDKTIwMTQgbWdyIEplcnp5IFdhxYJhc3plawovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBUeXB5IGRhbnljaAoKc3RydWN0IFNMZWwKewogIFNMZWwgKiBuZXh0OwogIGludCB2Owp9OwoKLy8gWm1pZW5uZSBnbG9iYWxuZQoKaW50IG0sIG47ICAgICAgICAgICAgICAgICAgICAgICAvLyBMaWN6YmEga3Jhd8SZZHppIGkgd2llcnpjaG/FgmvDs3cKU0xlbCAqKmdyYWY7ICAgICAgICAgICAgICAgICAvLyBUYWJsaWNhIGxpc3Qgc8SFc2llZHp0d2EKaW50ICpTOyAgICAgICAgICAgICAgICAgICAgICAgICAvLyBUYWJsaWNhLXN0b3MKaW50IHNwdHI7ICAgICAgICAgICAgICAgICAgICAgICAvLyBXc2thxbpuaWsgc3Rvc3UKYm9vbCAqdmlzaXRlZDsgICAgICAgICAgICAgICAgICAvLyBUYWJsaWNhIG9kd2llZHppbgoKLy8gUmVrdXJlbmN5am5hIHByb2NlZHVyYSB3eXpuYWN6YWrEhWNhIMWbY2llxbxraSBpIGN5a2xlIEhhbWlsdG9uYQovLyB2LXdpZXJ6Y2hvxYJlayBiaWXFvMSFY3kKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQp2b2lkIERGU0hhbWlsdG9uIChpbnQgdikKewogIGludCBpOwogIGJvb2wgdGVzdDsKICBTTGVsICpwOwoKICBTIFtzcHRyKytdID0gdjsgICAgICAgICAgICAgLy8gV2llcnpjaG/FgmVrIHYgbmEgc3RvcwogIGlmKHNwdHIgPCBuKSAgICAgICAgICAgICAgICAvLyBKZXN0IMWbY2llxbxrYSBIYW1pbHRvbmE/CiAgewogICAgdmlzaXRlZCBbdl0gPSB0cnVlOyAgICAgICAvLyBOaWUgbWEsIG9kd2llZHphbXkgdgogICAgZm9yKHAgPSBncmFmIFt2XTsgcDsgcCA9IHAtPm5leHQpIC8vIFByemVnbMSFZGFteSBzxIVzaWFkw7N3IHYKICAgICAgaWYoIXZpc2l0ZWQgW3AtPnZdKSBERlNIYW1pbHRvbiAocC0+dik7IC8vIFd5d2/FgmFuaWUgcmVrdXJlbmN5am5lCiAgICB2aXNpdGVkIFt2XSA9IGZhbHNlOyAgICAgIC8vIFd5Y29mdWplbXkgc2nEmSB6IHYKICB9CiAgZWxzZSAgICAgICAgICAgICAgICAgICAgICAgICAgLy8gSmVzdCDFm2NpZcW8a2EgSGFtaWx0b25hCiAgewogICAgdGVzdCA9IGZhbHNlOyAgICAgICAgICAgICAgIC8vIFpha8WCYWRhbXkgYnJhayBjeWtsdQogICAgZm9yKHAgPSBncmFmIFt2XTsgcDsgcCA9IHAtPm5leHQpIC8vIFByemVnbMSFZGFteSBzxIVzaWFkw7N3CiAgICAgIGlmKCEgKHAtPnYpKSAgICAgICAgICAvLyBKZcWbbGkgc8SFc2lhZGVtIGplc3Qgd2llcnpjaG/FgmVrIDAsIAogICAgICB7CiAgICAgICAgdGVzdCA9IHRydWU7ICAgICAgICAgICAgLy8gdG8gbWFteSBjeWtsCiAgICAgICAgYnJlYWs7CiAgICAgIH0KCiAgICBpZih0ZXN0KSBjb3V0IDw8ICJIYW1pbHRvbmlhbiBDeWNsZSA6IjsKICAgIGVsc2UgICAgIGNvdXQgPDwgIkhhbWlsdG9uaWFuIFBhdGggIDoiOwoKICAgIGZvcihpID0gMDsgaSA8IHNwdHI7IGkrKykgLy8gV3lwaXN1amVteSDFm2NpZcW8a8SZIEhhbWlsdG9uYQogICAgICBjb3V0IDw8IHNldHcgKDMpIDw8IFMgW2ldOwogICAgaWYodGVzdCkgY291dCA8PCBzZXR3ICgzKSA8PCAwOyAvLyBEbGEgY3lrbHUgZG9waXN1amVteSB3aWVyemNob8WCZWsgc3RhcnRvd3kKICAgIGNvdXQgPDwgZW5kbDsKICB9CiAgc3B0ci0tOyAgICAgICAgICAgICAgICAgICAgICAgLy8gV2llcnpjaG/FgmVrIHYgdXN1d2FteSB6ZSBzdG9zdQp9CgovLyAqKioqKioqKioqKioqKioqKioqKioqCi8vICoqKiBQUk9HUkFNIEfFgcOTV05ZICoqKgovLyAqKioqKioqKioqKioqKioqKioqKioqCgppbnQgbWFpbigpCnsKICBpbnQgaSwgdjEsIHYyOwogIFNMZWwgKnAsICpyOwoKICBjaW4gPj4gbiA+PiBtOyAvLyBDenl0YW15IGxpY3pixJkgd2llcnpjaG/FgmvDs3cgaSBrcmF3xJlkemkKCiAgLy8gVHdvcnp5bXkgdGFibGljZSBkeW5hbWljem5lCgogIGdyYWYgICAgPSBuZXcgU0xlbCAqIFtuXTsKICB2aXNpdGVkID0gbmV3IGJvb2wgW25dOwogIGZvcihpID0gMDsgaSA8IG47IGkrKykKICB7CiAgICBncmFmIFtpXSAgICA9IE5VTEw7CiAgICB2aXNpdGVkIFtpXSA9IGZhbHNlOwogIH0KICBTID0gbmV3IGludCBbbl07CiAgc3B0ciA9IDA7CgogIC8vIE9kY3p5dHVqZW15IGRlZmluaWNqZSBrcmF3xJlkemkgZ3JhZnUKCiAgZm9yKGkgPSAwOyBpIDwgbTsgaSsrKQogIHsKICAgIGNpbiA+PiB2MSA+PiB2MjsKICAgIHAgPSBuZXcgU0xlbDsKICAgIHAtPnYgPSB2MjsKICAgIHAtPm5leHQgPSBncmFmIFt2MV07CiAgICBncmFmIFt2MV0gPSBwOwogICAgcCA9IG5ldyBTTGVsOwogICAgcC0+diA9IHYxOwogICAgcC0+bmV4dCA9IGdyYWYgW3YyXTsKICAgIGdyYWYgW3YyXSA9IHA7CiAgfQoKICBjb3V0IDw8IGVuZGw7CgogIC8vIFd5xZt3aWV0bGFteSDFm2NpZcW8a2kgaSBjeWtsZSBIYW1pbHRvbmEKCiAgREZTSGFtaWx0b24gKDApOwoKICAvLyBVc3V3YW15IHptaWVubmUgZHluYW1pY3puZQoKICBkZWxldGUgW10gdmlzaXRlZDsKICBkZWxldGUgW10gUzsKCiAgZm9yKGkgPSAwOyBpIDwgbjsgaSsrKQogIHsKICAgIHAgPSBncmFmIFtpXTsKICAgIHdoaWxlKHApCiAgICB7CiAgICAgIHIgPSBwOwogICAgICBwID0gcC0+bmV4dDsKICAgICAgZGVsZXRlIHI7CiAgICB9CiAgfQoKICBkZWxldGUgW10gZ3JhZjsKCiAgcmV0dXJuIDA7fSA=

NSAxNAowIDIKMSAwCjEgMgoxIDMKMiAwCjIgMQozIDAKMyAxCjMgMgo0IDAKNCAxCjQgMgo0IDMKNCA0

5 14
0 2
1 0
1 2
1 3
2 0
2 1
3 0
3 1
3 2
4 0
4 1
4 2
4 3
4 4