// Badanie, czy graf zawiera cykl lub ścieżkę Eulera
// Data: 4.01.2014
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------------

program eulercp;

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

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    S : PSLel;  // 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 : PSLel;
begin
  new (e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

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

// Funkcja bada graf pod kątem posiadania cyklu lub ścieżki Eulera
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// Wynik:
// 0-graf nie zawiera ścieżki lub cyklu Eulera
// 1-graf zawiera ścieżkę Eulera
// 2-graf zawiera cykl Eulera
//-----------------------------------------------------------------
function isEulerian (n : integer; var graf : TList) : integer;
var
  no, nc, i, v, u : integer;
  S           : Stack;
  visited     : array of boolean;
  p           : PSLel;

begin
  i := 0;                     // Szukamy pierwszego wierzchołka z sąsiadami
  while(i < n) and (graf [i] = nil) do inc (i);
  if i = n then Exit (1);   // Graf nie ma krawędzi

  SetLength (visited, n);   // Tworzymy dynamicznie tablicę odwiedzin
  for v := 0 to n-1 do      // Wypełniamy ją wartościami false
    visited [v] := false;

  S.init;                     // Tworzymy stos

  no := 0;                    // Zerujemy licznik wierzchołków o stopniu nieparzystym

  S.push (i);               // Wierzchołek startowy na stos
  visited [i] := true;      // oznaczamy go jako odwiedzony

  // Uruchamiamy przejście DFS, aby wyznaczyć spójną składową zawierającą
  // wierzchołek startowy oraz policzyć stopnie wierzchołków i wyznaczyć
  // liczbę wierzchołków o stopniach nieparzystych

  while S.empty = false do
  begin
    v := S.top;               // Pobieramy do v wierzchołek ze stosu
    S.pop;                    // Pobrany wierzchołek usuwamy ze stosu

    nc := 0;                  // Licznik sąsiadów na zero

    p := graf [v];          // Przeglądamy sąsiadów wierzchołka v
    while p <> nil do
    begin
      inc (nc);             // Zwiększamy licznik sąsiadów
      u := p^.v;
      if not visited [u] then // Szukamy nieodwiedzonych sąsiadów
      begin
        visited [u] := true; // Zaznaczamy ich jako odwiedzonych
        S.push (u);         // i umieszczamy na stosie
      end;
      p := p^.next;           // Przechodzimy do następnego sąsiada na liście
    end;

    if nc mod 2 = 1 then inc (no); // Nieparzysta liczba sąsiadów?
  end;

  for v := i+1 to n-1 do  // Przeglądamy pozostałe wierzchołki grafu
    if(visited [v] = false) and (graf [v] <> nil) then
    begin
      SetLength (visited, 0); // Usuwamy tablicę odwiedzin
      Exit (0);               // graf nie jest spójny
    end;

  SetLength (visited, 0);   // Usuwamy tablicę odwiedzin

  if no = 0 then Exit (2);  // Graf zawiera cykl Eulera

  if no = 2 then Exit (1);  // Graf zawiera ścieżkę Eulera

  Exit (0);                 // Graf nie posiada ścieżki lub cyklu Eulera
end;

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

var
  n, m, i, v1, v2 : integer;
  p, r         : PSLel;
  A           : TList;

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

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

  // Tablicę 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;

  case isEulerian (n, A) of
    0: writeln('NOT AN EULERIAN GRAPH');
    1: writeln('SEMI-EULERIAN GRAPH');
    2: writeln('EULERIAN GRAPH');
  end;

  // Usuwamy tablicę list sąsiedztwa

  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.

// Badanie, czy graf zawiera cykl lub ścieżkę Eulera
// Data: 4.01.2014
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------------

#include <iostream>

using namespace std;

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

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

class Stack
{
  private:
    SLel * 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)
{
  SLel * e = new SLel;
  e->v    = v;
  e->next = S;
  S = e;
}

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

// Funkcja bada graf pod kątem posiadania cyklu lub ścieżki Eulera
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// Wynik:
// 0-graf nie zawiera ścieżki lub cyklu Eulera
// 1-graf zawiera ścieżkę Eulera
// 2-graf zawiera cykl Eulera
//-----------------------------------------------------------------
int isEulerian (int n, SLel ** graf)
{
  int no, nc, i, v, u;
  Stack S;
  bool * visited;
  SLel *p;

  for(i = 0; i < n && !graf [i]; i++); // Szukamy pierwszego wierzchołka z sąsiadami

  if(i == n) return 1;    // Graf nie ma krawędzi

  visited = new bool [n]; // Tworzymy dynamicznie tablicę odwiedzin
  for(v = 0; v < n; v++)  // Wypełniamy ją wartościami false
    visited [v] = false;

  no = 0;                   // Zerujemy licznik wierzchołków o stopniu nieparzystym

  S.push (i);             // Wierzchołek startowy na stos
  visited [i] = true;     // oznaczamy go jako odwiedzony

  // Uruchamiamy przejście DFS, aby wyznaczyć spójną składową zawierającą
  // wierzchołek startowy oraz policzyć stopnie wierzchołków i wyznaczyć
  // liczbę wierzchołków o stopniach nieparzystych

  while(!S.empty())
  {
    v = S.top();           // Pobieramy do v wierzchołek ze stosu
    S.pop();               // Pobrany wierzchołek usuwamy ze stosu

    nc = 0;                 // Licznik sąsiadów na zero

    for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka v
    {
      nC++;                 // Zwiększamy licznik sąsiadów
      u = p->v;
      if(!visited [u])  // Szukamy nieodwiedzonych sąsiadów
      {
        visited [u] = true; // Zaznaczamy ich jako odwiedzonych
        S.push (u);       // i umieszczamy na stosie
      }
    }

    if(nc % 2 == 1) no++; // Nieparzysta liczba sąsiadów?
  }

  for(v = i = 1; v < n; v++) // Przeglądamy pozostałe wierzchołki grafu
    if(!visited [v] && graf [v])
    {
      delete [] visited; // Usuwamy tablicę odwiedzin
      return 0;           // graf nie jest spójny
    }

  delete [] visited;     // Usuwamy tablicę odwiedzin

  if(!no) return 2;     // Graf zawiera cykl Eulera

  if(no == 2) return 1; // Graf zawiera ścieżkę Eulera

  return 0;               // Graf nie posiada ścieżki lub cyklu Eulera
}

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

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

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

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

  // Tablicę 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 SLel;    // 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 SLel;    // Krawędź w drugą stronę, bo graf jest nieskierowany
    p->v = v1;
    p->next = A [v2];
    A [v2] = p;
  }

  cout << endl;

  switch(isEulerian (n, A))
  {
    case 0: cout << "NOT AN EULERIAN GRAPH\n";
            break;
    case 1: cout << "SEMI-EULERIAN GRAPH\n";
            break;
    case 2: cout << "EULERIAN GRAPH\n";
            break;
  }

  // Usuwamy tablicę list sąsiedztwa

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

  delete [] A;

  return 0;}

' Badanie, czy graf zawiera cykl lub ścieżkę Eulera
' Data: 4.01.2014
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    S As SLel 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 SLel Ptr
  e = New SLel
  e->v    = v
  e->Next = S
  S = e
End Sub

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

' Funkcja bada graf pod kątem posiadania cyklu lub ścieżki Eulera
' n   -liczba wierzchołków w grafie
' graf-tablica list sąsiedztwa
' Wynik:
' 0-graf nie zawiera ścieżki lub cyklu Eulera
' 1-graf zawiera ścieżkę Eulera
' 2-graf zawiera cykl Eulera
'-----------------------------------------------------------------
Function isEulerian (ByVal n As integer, byval graf As SLel Ptr Ptr) As Integer

  Dim As Integer no, nc, i, v, u
  Dim As Stack S
  Dim As Byte Ptr visited
  Dim As SLel Ptr p

  i = 0
  while(i < n) AndAlso (graf [i] = 0)
  	 i += 1              ' Szukamy pierwszego wierzchołka z sąsiadami
  Wend

  If i = n Then Return 1  ' Graf nie ma krawędzi

  visited = New Byte [n] ' Tworzymy dynamicznie tablicę odwiedzin
  For v = 0 To n-1      ' Wypełniamy ją wartościami false
    visited [v] = 0
  Next
 
  no = 0                  ' Zerujemy licznik wierzchołków o stopniu nieparzystym

  S.push (i)            ' Wierzchołek startowy na stos
  visited [i] = 1       ' oznaczamy go jako odwiedzony

  ' Uruchamiamy przejście DFS, aby wyznaczyć spójną składową zawierającą
  ' wierzchołek startowy oraz policzyć stopnie wierzchołków i wyznaczyć
  ' liczbę wierzchołków o stopniach nieparzystych

  While S.empty() = 0
    v = S.top()          ' Pobieramy do v wierzchołek ze stosu
    S.pop()              ' Pobrany wierzchołek usuwamy ze stosu

    nc = 0                ' Licznik sąsiadów na zero

    p = graf [v]        ' Przeglądamy sąsiadów wierzchołka v
    While p
      nc += 1             ' Zwiększamy licznik sąsiadów
      u = p->v
      If visited [u] = 0 Then  ' Szukamy nieodwiedzonych sąsiadów
        visited [u] = 1 ' Zaznaczamy ich jako odwiedzonych
        S.push (u)      ' i umieszczamy na stosie
      End If
      p = p->Next         ' Następny sąsiad na liście
    Wend

    If nc Mod 2 = 1 Then no += 1 ' Nieparzysta liczba sąsiadów?
  Wend

  For v = i+1 To n-1  ' Przeglądamy pozostałe wierzchołki grafu
    if(visited [v] = 0) AndAlso (graf [v] <> 0) Then
      Delete [] visited  ' Usuwamy tablicę odwiedzin
      Return 0            ' graf nie jest spójny
    End If
  Next

  Delete [] visited      ' Usuwamy tablicę odwiedzin

  If no = 0 Then Return 2 ' Graf zawiera cykl Eulera

  If no = 2 Then return 1 ' Graf zawiera ścieżkę Eulera

  Return 0                ' Graf nie posiada ścieżki lub cyklu Eulera
End Function

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

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr A

Open Cons For Input As #1

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

A = new SLel 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 SLel    ' 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 SLel    ' Krawędź w drugą stronę, bo graf jest nieskierowany
  p->v = v1
  p->next = A [v2]
  A [v2] = p
Next

Close #1

Print

Select Case isEulerian (n, A)
  case 0
    Print "NOT AN EULERIAN GRAPH"
  Case 1
    Print "SEMI-EULERIAN GRAPH"
  Case 2
    Print "EULERIAN GRAPH"
End Select

' Usuwamy tablicę list sąsiedztwa

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

Delete [] A

End

// Badanie istnienia cyklu lub ścieżki Eulera
// Data: 3.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program scc;

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

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

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

// Zmienne globalne
//-----------------
var
  n, m, cvn: integer;
  VN, VLow, Vind, Voutd, C  : array of integer;
  VS       : array of boolean;
  S        : Stack;
  graf     : array of PSLel;

//---------------------
// Metody obiektu Stack
//---------------------

// 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 : PSLel;
begin
  new (e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

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

// Zwraca mniejszą z dwóch liczb
//------------------------------
function min (a, b : integer) : integer;
begin
  if a < b then min := a else min := b;
end;

// Procedura wykonująca przejście DFS i wyznaczająca
// silnie spójną składową oraz stopnie wierzchołków
// v-wierzchołek startowy dla DFS
//---------------------------------------------------
procedure DFSscc (v : integer);
var
  u : integer;
  p : PSLel;
begin
  inc (cvn);                  // Zwiększamy numer wierzchołka
  VN [v]    := cvn;           // Numerujemy bieżący wierzchołek
  VLow [v]  := cvn;           // Ustalamy wstępnie parametr Low
  S.push (v);                 // Wierzchołek na stos
  VS [v]    := true;          // Zapamiętujemy, że v jest na stosie

  p := graf [v];              // Przeglądamy listę sąsiadów
  while p <> nil do
  begin
    inc (Voutd [v]);        // Wyznaczamy stopień wychodzący
    inc (Vind [p^.v]);      // i wchodzący
    if VN [p^.v] = 0 then     // Jeśli sąsiad jest nieodwiedzony, to
    begin
      DFSscc (p^.v);          // wywołujemy dla niego rekurencyjnie DFS
      VLow [v] := min (VLow [v], VLow [p^.v]); // i obliczamy parametr Low dla v
    end
    else if VS [p^.v] then    // jeśli sąsiad odwiedzony, lecz wciąż na stosie, 
      VLow [v] := min (VLow [v], VN [p^.v]); // to wyznaczamy parametr Low dla v
    p := p^.next;
  end;

  if VLow [v] = VN [v] then // Sprawdzamy, czy mamy kompletną składową
  begin
    repeat
      u := S.top;               // Pobieramy wierzchołek ze stosu
      S.pop;                    // Pobrany wierzchołek usuwamy ze stosu
      VS [u] := false;        // Zapamiętujemy, że nie ma go już na stosie
      C [u] := v;             // Zapamiętujemy numer silnie spójnej składowej
    until u = v;                // Kontynuujemy aż do korzenia składowej
  end;
end;

// Funkcja bada istnienie cyklu lub ścieżki Eulera
// Zwraca:
// 0-brak cyklu i ścieżki
// 1-jest ścieżka Eulera
// 2-jest cykl Eulera
//------------------------------------------------
function isEulerian : integer;
var
  v, cinout, coutin : integer;
begin
  cvn := 0;                  // Zerujemy numer wierzchołka

  for v := 0 to n-1 do     // Przeglądamy kolejne wierzchołki
    if VN [v] = 0 then DFSscc (v); // W wierzchołku nieodwiedzonym uruchamiamy DFS

  v := 0;                    // Szukamy pierwszego wierzchołka o niezerowym stopniu
  while(v < n) and (Vind [v]+Voutd [v] = 0) do inc (v);
  if v = n then Exit (0);  // Graf jest pusty

  cvn := C [v];            // Zapamiętujemy numer silnie spójnej składowej
  cinout := 0;               // Licznik wierzchołków o większym o 1 stopniu wchodzącym
  coutin := 0;               // Licznik wierzchołków o większym o 1 stopniu wychodzącym

  while v < n do             // Przeglądamy graf
  begin
    if Vind [v] = Voutd [v] > 0 then
    begin
      if C [v] <> cvn then Exit (0); // graf nie jest silnie spójny
      if Vind [v] <> Voutd [v] then
      begin
        if Vind [v]-Voutd [v] = 1 then
        begin
          inc (cinout);
          if cinout > 1 then Exit (0); // Za dużo wierzchołków o nierównych stopniach
        end
        else if Voutd [v]-Vind [v] = 1 then
        begin
          inc (coutin);
          if coutin > 1 then Exit (0); // Za dużo wierzchołków o nierównych stopniach
        end
        else Exit (0); // Stopnie różnią się o więcej niż 1
      end;
    end;
    inc (v);
  end;

  // Analizujemy stan liczników

  if cinout = 1 then Exit (1) // mamy ścieżkę Eulera
  else               Exit (2) // mamy cykl Eulera
end;

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

var
  i, v, u      : integer;
  p, r        : PSLel;

begin
  S.init;                  // Tworzymy pusty stos

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

  SetLength (graf, n);   // Tworzymy tablice dynamiczne
  SetLength (VN, n);
  SetLength (VS, n);
  SetLength (VLow, n);
  SetLength (Vind, n);
  SetLength (Voutd, n);
  SetLength (C, n);

  // Inicjujemy tablice

  for i := 0 to n-1 do
  begin
    graf [i]  := nil;
    VN [i]    := 0;
    Vind [i]  := 0;
    Voutd [i] := 0;
    VS [i]    := false;
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m-1 do
  begin
    read (v, u);         // Wierzchołki tworzące krawędź
    new (p);             // Tworzymy nowy element
    p^.v := u;             // Numerujemy go jako u
    p^.next := graf [v]; // i dodajemy na początek listy graf [v]
    graf [v] := p;
  end;

  writeln;

  // Badamy graf

  case isEulerian of
    0: writeln('NOT AN EULERIAN GRAPH');
    1: writeln('SEMI-EULERIAN GRAPH');
    2: writeln('EULERIAN GRAPH');
  end;

  // Usuwamy zmienne dynamiczne

  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);
  SetLength (VN, 0);
  SetLength (VLow, 0);
  SetLength (VS, 0);
  SetLength (Vind, 0);
  SetLength (Voutd, 0);
  SetLength (C, 0);
  S.destroy;
end.

// Badanie istnienia cyklu lub ścieżki Eulera
// Data: 3.02.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

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

// Definicja typu obiektowego Stack
//---------------------------------
class Stack
{
  private:
    SLel * S;   // lista przechowująca stos

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

// Zmienne globalne
//-----------------

int n, m, cvn, *VN, *VLow, *Vind, *Voutd, *C;
bool *VS;
Stack S;
SLel **graf;

//---------------------
// 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)
{
  SLel * e = new SLel;
  e->v    = v;
  e->next = S;
  S = e;
}

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

// Procedura wykonująca przejście DFS i wyznaczająca
// silnie spójną składową oraz stopnie wierzchołków
// v-wierzchołek startowy dla DFS
//---------------------------------------------------
void DFSscc (int v)
{
  int u;
  SLel * p;

  VN [v] = VLow [v] = ++cvn; // Ustalamy wstępnie parametr Low
  S.push (v);             // Wierzchołek na stos
  VS [v] = true;          // Zapamiętujemy, że v jest na stosie

  for(p = graf [v];p;p = p->next) // Przeglądamy listę sąsiadów
  {
    ++Voutd [v];          // Wyznaczamy stopień wychodzący
    ++Vind [p->v];        // i wchodzący
    if(!VN [p->v])      // Jeśli sąsiad jest nieodwiedzony, to
    {
      DFSscc (p->v);      // wywołujemy dla niego rekurencyjnie DFS
      VLow [v] = min (VLow [v], VLow [p->v]); // i obliczamy parametr Low dla v
    }
    else if(VS [p->v])  // jeśli sąsiad odwiedzony, lecz wciąż na stosie, 
      VLow [v] = min (VLow [v], VN [p->v]); // to wyznaczamy parametr Low dla v
  }

  if(VLow [v] == VN [v]) // Sprawdzamy, czy mamy kompletną składową
    do
    {
      u = S.top();         // Pobieramy wierzchołek ze stosu
      S.pop();             // Pobrany wierzchołek usuwamy ze stosu
      VS [u] = false;     // Zapamiętujemy, że nie ma go już na stosie
      C [u] = v;          // Zapamiętujemy numer silnie spójnej składowej
    } while(u != v);      // Kontynuujemy aż do korzenia składowej
}

// Funkcja bada istnienie cyklu lub ścieżki Eulera
// Zwraca:
// 0-brak cyklu i ścieżki
// 1-jest ścieżka Eulera
// 2-jest cykl Eulera
//------------------------------------------------
int isEulerian()
{
  int v, cinout, coutin;

  cvn = 0;                  // Zerujemy numer wierzchołka

  for(v = 0; v < n; v++)  // Przeglądamy kolejne wierzchołki
    if(!VN [v]) DFSscc (v); // W wierzchołku nieodwiedzonym uruchamiamy DFS

  // Szukamy pierwszego wierzchołka o niezerowym stopniu

  for(v = 0; (v < n) && ! (Vind [v] = Voutd [v]);v++);

  if(v == n) return 0;    // Graf jest pusty

  cvn = C [v];            // Zapamiętujemy numer silnie spójnej składowej
  cinout = coutin = 0;      // Zerujemy liczniki

  for(;v < n;v++)         // Przeglądamy graf
    if(Vind [v] = Voutd [v])
    {
      if(C [v] != cvn) return 0; // graf nie jest silnie spójny
      if(Vind [v] != Voutd [v])
      {
        if(Vind [v]-Voutd [v] == 1)
        {
          if(++cinout > 1) return 0; // Za dużo wierzchołków o nierównych stopniach
        }
        else if(Voutd [v]-Vind [v] == 1)
        {
          if(++coutin > 1) return 0; // Za dużo wierzchołków o nierównych stopniach
        }
        else return 0;        // Stopnie różnią się o więcej niż 1
      }
    }

  // Analizujemy stan liczników

  if(cinout == 1) return 1; // mamy ścieżkę Eulera
  else              return 2; // mamy cykl Eulera
}

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

int main()
{
  int i, v, u;
  SLel *p, *r;

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

  graf  = new SLel * [n]; // Tworzymy tablice dynamiczne
  VN    = new int [n];
  VS    = new bool [n];
  VLow  = new int [n];
  Vind  = new int [n];
  Voutd = new int [n];
  C     = new int [n];

  // Inicjujemy tablice

  for(i = 0; i < n; i++)
  {
    graf [i] = NULL;
    VN [i]   = Vind [i] = Voutd [i] = 0;
    VS [i]   = false;
  }

  // Odczytujemy kolejne definicje krawędzi.

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;        // Wierzchołki tworzące krawędź
    p = new SLel;      // Tworzymy nowy element
    p->v = u;             // Numerujemy go jako u
    p->next = graf [v]; // i dodajemy na początek listy graf [v]
    graf [v] = p;
  }

  cout << endl;

  // Badamy graf

  switch(isEulerian())
  {
    case 0: cout << "NOT AN EULERIAN GRAPH\n"; break;
    case 1: cout << "SEMI-EULERIAN GRAPH\n"; break;
    case 2: cout << "EULERIAN GRAPH\n"; break;
  }

  // Usuwamy zmienne dynamiczne

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

  delete [] graf;
  delete [] VN;
  delete [] VLow;
  delete [] VS;
  delete [] Vind;
  delete [] Voutd;
  delete [] C;

  return 0;}

' Badanie istnienia cyklu lub ścieżki Eulera
' Data: 3.02.2014
' (C)2014 mgr Jerzy Wałaszek
'-------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu

Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    S As SLel 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

' Zmienne globalne
'-----------------

Dim Shared As Integer n, m, cvn
Dim Shared As Integer Ptr VN, VLow, Vind, Voutd, C
Dim Shared As Byte Ptr VS
Dim Shared As Stack S
Dim Shared As SLel Ptr Ptr graf

'---------------------
' 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 SLel Ptr
  e = New SLel
  e->v    = v
  e->Next = S
  S = e
End Sub

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

' Funkcja zwraca mniejszą z liczb a i b
'--------------------------------------
Function min (ByVal a As Integer, ByVal b As Integer) As Integer
  If a < b Then
    Return a
  Else
    Return b
  EndIf
End Function

' Procedura wykonująca przejście DFS i wyznaczająca
' silnie spójną składową oraz stopnie wierzchołków
' v-wierzchołek startowy dla DFS
'---------------------------------------------------
sub DFSscc (ByVal v As Integer)

  Dim As Integer u
  Dim As SLel Ptr p

  cvn += 1
  VN [v] = cvn
  VLow [v] = cvn            ' Ustalamy wstępnie parametr Low
  S.push (v)                ' Wierzchołek na stos
  VS [v] = 1                ' Zapamiętujemy, że v jest na stosie

  p = graf [v]
  While p                     ' Przeglądamy listę sąsiadów
    Voutd [v] += 1          ' Wyznaczamy stopień wychodzący
    Vind [p->v] += 1        ' i wchodzący
    If VN [p->v] = 0 Then   ' Jeśli sąsiad jest nieodwiedzony, to
      DFSscc (p->v)         ' wywołujemy dla niego rekurencyjnie DFS
      VLow [v] = min (VLow [v], VLow [p->v]) ' i obliczamy parametr Low dla v
    ElseIf VS [p->v] = 1 Then ' jeśli sąsiad odwiedzony, lecz wciąż na stosie, 
      VLow [v] = min (VLow [v], VN [p->v]) ' to wyznaczamy parametr Low dla v
    End If
    p = p->Next
  Wend

  If VLow [v] = VN [v] Then ' Sprawdzamy, czy mamy kompletną składową
    Do
      u = S.top()            ' Pobieramy wierzchołek ze stosu
      S.pop()                ' Pobrany wierzchołek usuwamy ze stosu
      VS [u] = 0            ' Zapamiętujemy, że nie ma go już na stosie
      C [u] = v             ' Zapamiętujemy numer silnie spójnej składowej
    Loop While u <> v         ' Kontynuujemy aż do korzenia składowej
  End If
End Sub

' Funkcja bada istnienie cyklu lub ścieżki Eulera
' Zwraca:
' 0-brak cyklu i ścieżki
' 1-jest ścieżka Eulera
' 2-jest cykl Eulera
'------------------------------------------------
Function isEulerian() As Integer

  Dim As Integer v, cinout, coutin

  cvn = 0                     ' Zerujemy numer wierzchołka

  For v = 0 To n-1          ' Przeglądamy kolejne wierzchołki
    If VN [v] = 0 then DFSscc (v)  ' W wierzchołku nieodwiedzonym uruchamiamy DFS
  Next
 
  ' Szukamy pierwszego wierzchołka o niezerowym stopniu

  v = 0
  while(v < n) AndAlso (Vind [v]+Voutd [v] = 0)
    v += 1
  Wend

  If v = n then Return 0      ' Graf jest pusty

  cvn = C [v]               ' Zapamiętujemy numer silnie spójnej składowej
  cinout = 0                  ' Zerujemy liczniki
  coutin = 0
 
  While v < n                 ' Przeglądamy graf
    If Vind [v] = Voutd [v] > 0 Then
      If C [v] <> cvn Then Return 0 ' graf nie jest silnie spójny
      If Vind [v] <> Voutd [v] Then
        If Vind [v]-Voutd [v] = 1 Then
          cinout += 1
          If cinout > 1 then return 0 ' Za dużo wierzchołków o nierównych stopniach
        ElseIf Voutd [v]-Vind [v] = 1 Then
          coutin += 1
          If coutin > 1 Then Return 0 ' Za dużo wierzchołków o nierównych stopniach
        Else
          Return 0            ' Stopnie różnią się o więcej niż 1
        End If
      End If
    End If
    v += 1
  Wend
 
  ' Analizujemy stan liczników

  If cinout = 1 Then Return 1 ' mamy ścieżkę Eulera
  return 2                    ' mamy cykl Eulera
End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer i, v, u
Dim As SLel Ptr p, r

Open Cons For Input As #1

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

graf  = New SLel Ptr [n] ' Tworzymy tablice dynamiczne
VN    = New Integer [n]
VS    = New Byte [n]
VLow  = New Integer [n]
Vind  = New Integer [n]
Voutd = New Integer [n]
C     = New Integer [n]

' Inicjujemy tablice

For i = 0 To n-1
  graf [i]  = 0
  VN [i]    = 0
  Vind [i]  = 0
  Voutd [i] = 0
  VS [i]    = 0
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1, v, u       ' Wierzchołki tworzące krawędź
  p = New SLel      ' Tworzymy nowy element
  p->v = u             ' Numerujemy go jako w
  p->next = graf [v] ' Dodajemy go na początek listy A [v]
  graf [v] = p
Next

Close #1

Print

' Badamy graf

Select Case isEulerian()
  Case 0
    Print "NOT AN EULERIAN GRAPH"
  Case 1
    Print "SEMI-EULERIAN GRAPH"
  Case 2
    Print "EULERIAN GRAPH"
End Select

' Usuwamy tablice dynamiczne

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

Delete [] graf
Delete [] VN
Delete [] VLow
Delete [] VS
Delete [] Vind
Delete [] Voutd
Delete [] C

End