// Wyszukiwanie cykli w grafie nieskierowanym
// Data: 22.12.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------------------

program fndcycles;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// Definicja typu obiektowego stack
//---------------------------------
stack = object
  private
    S : PslistEl;  // lista przechowująca stos

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push ( v : integer );
    procedure  pop;
end;

// Konstruktor
//------------
constructor stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function stack.top : integer;
begin
  top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure stack.push ( v : integer );
var
  e : PslistEl;
begin
  new ( e );
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure stack.pop;
var
  e :PslistEl;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose ( e );
  end;
end;

// Funkcja rekurencyjna wyszukująca cykl
//--------------------------------------
function DFSfindCycle ( var graf : TList; v, w : integer; var S : stack;
                      var visited : array of boolean ) : boolean;
var
  u : integer;
  p : PslistEl;
begin
  visited [ w ] := true;         // Oznaczamy wierzchołek jako odwiedzony
  p := graf [ w ];               // Rozpoczynamy przeglądanie sąsiadów
  while p <> nil do
  begin
    u := p^.v;                   // u - numer wierzchołka będącego sąsiadem
    if u <> S.top then           // Pomijamy wierzchołek, z którego przyszliśmy
    begin
      S.push ( w );              // Na stos wierzchołek bieżący
      if u = v then Exit ( true ); // Cykl znaleziony, kończymy
      if( visited [ u ] = false ) and DFSfindCycle ( graf, v, u, S, visited ) then Exit ( true );
      S.pop;
    end;
    p := p^.next;
  end;
  Exit ( false );
end;

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

var
  n, m, i, j, u, v1, v2 : integer;
  visited  : array of boolean;
  S        : stack;
  p, r     : PslistEl;
  A        : TList;

begin
  read ( n, m );           // Czytamy liczbę wierzchołków i krawędzi

  SetLength ( A, n );      // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read ( v1, v2 );       // Wierzchołek startowy i końcowy krawędzi
    new ( p );             // Tworzymy nowy element
    p^.v := v2;            // Numerujemy go jako v2
    p^.next := A [ v1 ];   // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] := p;
    new ( p );             // Krawędź w drugą stronę, bo graf jest nieskierowany
    p^.v := v1;
    p^.next := A [ v2 ];
    A [ v2 ] := p;
  end;

  writeln;

  SetLength ( visited, n );      // Tworzymy tablicę odwiedzin
  S.init;                        // Tworzymy stos wierzchołków
  for i := 0 to n - 1 do         // Przechodzimy przez kolejne wierzchołki grafu
  begin
    for j := 0 to n - 1 do       // Zerujemy tablicę odwiedzin
      visited [ j ] := false;

    S.push ( -1 );               // Na stos znacznik początku ścieżki

    write ( i );                 // Wypisujemy wierzchołek startowy cyklu

    if DFSfindCycle ( A, i, i, S, visited ) = false then // Szukamy cyklu
    begin
      S.pop;                     // Usuwamy ze stosu początek ścieżki
      writeln ( ' - no cycle' ); // Komunikat
    end
    else
      while S.empty = false do   // Wypisujemy cykl, jeśli istnieje
      begin
        u := S.top; S.pop;       // Pobieramy ze stosu numer wierzchołka
        if u > -1 then write ( ' ', u )// i wypisujemy go
        else           writeln;
      end;
  end;

  // Usuwamy dynamiczne struktury danych

  SetLength ( visited, 0 );

  S.destroy;

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

  SetLength ( A, 0 );
end.

// Wyszukiwanie cykli w grafie nieskierowanym
// Data: 22.12.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu

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

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  public:
    stack( );      // konstruktor
    ~stack( );     // destruktor
    bool empty ( void );
    int  top ( void );
    void push ( int v );
    void pop ( void );
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------
stack::stack( )
{
  S = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack( )
{
  while( S ) pop( );
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool stack::empty ( void )
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int stack::top ( void )
{
  return S->v;
}

// Zapisuje na stos
//-----------------
void stack::push ( int v )
{
  slistEl * e = new slistEl;
  e->v    = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void stack::pop ( void )
{
  if( S )
  {
    slistEl * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja rekurencyjna wyszukująca cykl
//--------------------------------------
bool DFSfindCycle ( slistEl ** graf, int v, int w, stack & S, bool * visited )
{
  int u;
  slistEl * p;

  visited [ w ] = true;         // Oznaczamy wierzchołek jako odwiedzony
  p = graf [ w ];               // Rozpoczynamy przeglądanie sąsiadów
  while( p )
  {
    u = p->v;                   // u - numer wierzchołka będącego sąsiadem
    if( u != S.top( ) )         // Pomijamy wierzchołek, z którego przyszliśmy
    {
      S.push ( w );             // Na stos wierzchołek bieżący
      if( u == v ) return true; // Cykl znaleziony, kończymy
      if( !visited [ u ] && DFSfindCycle ( graf, v, u, S, visited ) ) return true;
      S.pop( );
    }
    p = p->next;
  }
  return false;
}

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

int main( )
{
  int n, m, i, j, u, v1, v2;
  slistEl * p, * r, ** A;
  bool * visited;
  stack S;

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

  A = new slistEl * [ n ]; // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = v2;          // Numerujemy go jako v2
    p->next = A [ v1 ]; // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] = p;
    p = new slistEl;    // Krawędź w drugą stronę, bo graf jest nieskierowany
    p->v = v1;
    p->next = A [ v2 ];
    A [ v2 ] = p;
  }

  cout << endl;

  visited = new bool [ n ];      // Tworzymy tablicę odwiedzin

  for( i = 0; i < n; i++ )       // Przechodzimy przez kolejne wierzchołki grafu
  {
    for( j = 0; j < n; j++ )     // Zerujemy tablicę odwiedzin
      visited [ j ] = false;

    S.push ( -1 );               // Na stos znacznik początku ścieżki

    cout << i;                   // Wypisujemy wierzchołek startowy cyklu

    if( !DFSfindCycle ( A, i, i, S, visited ) ) // Szukamy cyklu
    {
      S.pop( );                  // Usuwamy ze stosu początek ścieżki
      cout << " - no cycle\n";   // Komunikat
    }
    else
      while( !S.empty( ) )       // Wypisujemy cykl, jeśli istnieje
      {
        u = S.top( ); S.pop( );  // Pobieramy ze stosu numer wierzchołka
        if( u > -1 ) cout << " " << u; // i wypisujemy go
        else       cout << endl;
      }
  }

  // Usuwamy dynamiczne struktury danych

  delete [ ] visited;

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

  delete [ ] A;

  return 0;
}

' Wyszukiwanie cykli w grafie nieskierowanym
' Data: 22.12.2013
' (C)2013 mgr Jerzy Wałaszek
'-------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  Public:
    Declare Constructor( )
    Declare Destructor( )
    Declare Function empty( ) As Integer
    Declare Function top As Integer
    Declare Sub push ( ByVal v As Integer )
    Declare Sub pop( )
End Type

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------
Constructor stack( )
  S = 0
End Constructor

' Destruktor
'-----------
Destructor stack( )
  While S
    pop( )
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty( ) As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function stack.top( ) As Integer
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub stack.push ( ByVal v As Integer )
  Dim e As slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop( )
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

' Funkcja rekurencyjna wyszukująca cykl
'--------------------------------------
Function DFSfindCycle ( ByVal graf As slistEl Ptr Ptr,_
	                  ByVal v As integer, ByVal w As integer,_
	                  ByRef S As stack,_
	                  ByVal visited As Integer Ptr ) As Integer

  Dim As Integer u
  Dim As slistEl Ptr p

  visited [ w ] = 1            ' Oznaczamy wierzchołek jako odwiedzony
  p = graf [ w ]               ' Rozpoczynamy przeglądanie sąsiadów
  While p
    u = p->v                   ' u - numer wierzchołka będącego sąsiadem
    If u <> S.top( ) Then      ' Pomijamy wierzchołek, z którego przyszliśmy
      S.push ( w )             ' Na stos wierzchołek bieżący
      If u = v Then Return 1   ' Cykl znaleziony, kończymy
      if( visited [ u ] = 0 ) AndAlso ( DFSfindCycle ( graf, v, u, S, visited ) = 1 ) Then Return 1
      S.pop( )
    End If
    p = p->Next
  Wend
  Return 0
End Function

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

Dim As Integer n, m, i, j, u, v1, v2
Dim As slistEl Ptr p, r
Dim As slistEl Ptr Ptr A
Dim As Integer Ptr visited
Dim As stack S

Open Cons For Input As #1

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

A = new slistEl Ptr [ n ] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

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

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1, v1, v2     ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = v2            ' Numerujemy go jako v2
  p->next = A [ v1 ]   ' Dodajemy go na początek listy A [ v1 ] 
  A [ v1 ] = p
  p = new slistEl      ' Krawędź w drugą stronę, bo graf jest nieskierowany
  p->v = v1
  p->next = A [ v2 ] 
  A [ v2 ] = p
Next

Close #1

Print

visited = New Integer [ n ]    ' Tworzymy tablicę odwiedzin

For i = 0 To n - 1             ' Przechodzimy przez kolejne wierzchołki grafu
  For j = 0 To n - 1           ' Zerujemy tablicę odwiedzin
    visited [ j ] = 0
  Next
  
  S.push ( -1 )                ' Na stos znacznik początku ścieżki

  Print i;                     ' Wypisujemy wierzchołek startowy cyklu

  If DFSfindCycle ( A, i, i, S, visited ) = 0 Then ' Szukamy cyklu
    S.pop( )                   ' Usuwamy ze stosu początek ścieżki
    Print " - no cycle"        ' Komunikat
  Else
    While S.empty( ) = 0       ' Wypisujemy cykl, jeśli istnieje
      u = S.top( ): S.pop( )   ' Pobieramy ze stosu numer wierzchołka
      If u > -1 Then
        Print u;               ' i wypisujemy go
      Else
        Print
      End If
    Wend
  End If
Next

' Usuwamy dynamiczne struktury danych

Delete [ ] visited

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

Delete [ ] A

End