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