Cykliczność grafu

// Badanie cykliczności niespójnego grafu nieskierowanego
// Data: 14.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------------------

program project1;

// 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 bada cykliczność składowej grafu
//-----------------------------------------
function isComponentCyclic(var G : TList; v : integer; var visited : array of boolean) : boolean;
var
  S : stack;                    // Stos
  p : PslistEl;                 // Wskaźnik elementu listy
  w,z : integer;                // Zmienne pomocnicze
begin
  S.init;                       // Tworzymy pusty stos
  S.push(v); S.push(-1);        // Na stos wierzchołek startowy i -1
  visited[v] := true;           // Oznaczamy wierzchołek startowy jako odwiedzony
  while S.empty = false do      // W pętli przechodzimy graf za pomocą DFS
  begin
    w := S.top; S.pop;          // Pobieramy ze stosu wierzchołek z którego przyszliśmy
    v := S.top; S.pop;          // oraz wierzchołek bieżący
    p := G[v];                  // Przeglądamy jego listę sąsiadów
    while p <> nil do
    begin
      z := p^.v;                // Numer sąsiada
      if visited[z] = false then
      begin
        S.push(z); S.push(v);   // Sąsiada nieodwiedzonego umieszczamy na stosie
        visited[z] := true;
      end
      else if z <> w then       // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem
      begin                     // z którego przyszliśmy, to odkryliśmy cykl
        S.destroy;
        Exit(true);             // Kończymy z wynikiem true
      end;
      p := p^.next;
    end;
  end;
  S.destroy;
  Exit(false);                  // Kończymy z wynikiem false
end;

// Funkcja bada cykliczność grafu
//-------------------------------
function isCyclic(n : integer; var G : Tlist) : boolean;
var
  i : integer;
  visited : array of boolean;
begin
  SetLength(visited,n);         // Tworzymy tablicę odwiedzin
  for i := 0 to n - 1 do
    visited[i] := false;        // Tablicę zerujemy
  for i := 0 to n - 1 do        // Szukamy wierzchołka startowego
    if (visited[i] = false) and (isComponentCyclic(G,i,visited) = true) then
    begin
      SetLength(visited,0);
      Exit(true);               // Cykl znaleziony, kończymy z true
    end;
  SetLength(visited,0);
  Exit(false);                  // Graf nie posiada cyklu, kończymy z false
end; 

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

var
  n,m,i,v1,v2 : integer;
  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;

  if isCyclic(n,A) then writeln('CYCLIC GRAPH')
  else                  writeln('ACYCLIC GRAPH');

  // 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 cykliczności niespójnego grafu nieskierowanego
// Data: 14.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 bada cykliczność składowej grafu
//-----------------------------------------
bool isComponentCyclic(slistEl ** G, int v, bool * visited)
{
  stack S;                      // Stos
  slistEl * p;                  // Wskaźnik elementu listy
  int w,z;                      // Zmienne pomocnicze

  S.push(v); S.push(-1);        // Na stos wierzchołek startowy i -1
  visited[v] = true;            // Wierzchołek startowy oznaczamy jako odwiedzony
  while(!S.empty())             // W pętli przechodzimy graf za pomocą DFS
  {
    w = S.top(); S.pop();       // Pobieramy ze stosu wierzchołek z którego przyszliśmy
    v = S.top(); S.pop();       // oraz wierzchołek bieżący

    for(p = G[v]; p; p = p->next) // Przeglądamy listę sąsiadów
    {
      z = p->v;                 // Numer sąsiada
      if(!visited[z])
      {
        S.push(z); S.push(v);   // Sąsiada nieodwiedzonego umieszczamy na stosie
        visited[z] = true;
      }
      else if(z != w)           // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem
                                // z którego przyszliśmy, to odkryliśmy cykl
        return true;            // Kończymy z wynikiem true
    }
  }
  return false;                 // Kończymy z wynikiem false
}

// Funkcja bada cykliczność grafu
//-------------------------------
bool isCyclic(int n, slistEl ** G)
{
  int i;
  bool * visited;

  visited = new bool [n];       // Tworzymy tablicę odwiedzin
  for(i = 0; i < n; i++)
    visited[i] = false;         // Tablicę zerujemy
  for(i = 0; i < n; i++)        // Szukamy wierzchołka startowego
    if(!visited[i] && isComponentCyclic(G,i,visited))
    {
      delete [] visited;
      return true;              // Cykl znaleziony, kończymy z true
    }
  delete [] visited;
  return false;                 // Graf nie posiada cyklu, kończymy z false
}

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

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

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

  if(isCyclic(n,A)) cout << "CYCLIC GRAPH";
  else              cout << "ACYCLIC GRAPH";

  cout << endl;

  // 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 cykliczności niespójnego grafu nieskierowanego
' Data: 14.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 bada cykliczność składowej grafu
'-----------------------------------------
Function isComponentCyclic(ByVal G As slistEl Ptr Ptr, ByVal v As Integer, ByVal visited As Integer Ptr) As Integer

  Dim As stack S                ' Stos
  Dim As slistEl Ptr p          ' Wskaźnik elementu listy
  Dim As Integer w,z            ' Zmienne pomocnicze

  S.push(v): S.push(-1)         ' Na stos wierzchołek startowy i -1
  visited[v] = 1                ' Wierzchołek oznaczamy jako odwiedzony
  While S.empty() = 0           ' W pętli przechodzimy graf za pomocą DFS
 
    w = S.top(): S.pop()        ' Pobieramy ze stosu wierzchołek z którego przyszliśmy
    v = S.top(): S.pop()        ' oraz wierzchołek bieżący
    p = G[v]
    While p                     ' Przeglądamy jego listę sąsiadów
      z = p->v                  ' Numer sąsiada
      If visited[z] = 0 Then
        S.push(z): S.push(v)    ' Sąsiada nieodwiedzonego umieszczamy na stosie
        visited[z] = 1
      ElseIf z <> w Then        ' Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem
                                ' z którego przyszliśmy, to odkryliśmy cykl
        Return 1                ' Kończymy z wynikiem true
      EndIf
      p = p->Next
    Wend
  Wend
  
  Return 0                      ' W grafie nie ma cykli. Kończymy z wynikiem false
End Function

' Funkcja bada cykliczność grafu
'-------------------------------
Function isCyclic(ByVal n As Integer, ByVal G As slistEl Ptr Ptr) As Integer
  
  Dim As Integer i
  Dim As Integer ptr visited

  visited = new Integer [n]     ' Tworzymy tablicę odwiedzin
  For i = 0 To n - 1
    visited[i] = 0              ' Tablicę zerujemy
  Next
  For i = 0 To n - 1            ' Szukamy wierzchołka startowego
    If (visited[i] = 0) AndAlso (isComponentCyclic(G,i,visited) = 1) Then
      Delete [] visited
      Return 1                  ' Cykl znaleziony, kończymy z true
    End If
  Next
  Delete [] visited
  Return 0                      ' Graf nie posiada cyklu, kończymy z false
End Function

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

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

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

If isCyclic(n,A) Then
  Print "CYCLIC GRAPH"
Else
  Print "ACYCLIC GRAPH"
EndIf

' 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 cykliczności grafu skierowanego
// Data: 19.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

program project1;

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

TList = array of PslistEl;

// Funkcje badające cykliczność grafu
//-----------------------------------
function isGraphCyclic(var G : TList; v : integer; var visited : array of char) : boolean;
var
  p : PslistEl;                 // Wskaźnik elementu listy
  u : integer;
begin
  visited[v] := 'G';            // Kolorujemy wierzchołek na szaro
  p := G[v];                    // Sprawdzamy kolejnych sąsiadów
  while p <> nil do
  begin
    u := p^.v;                  // u <-- numer sąsiada
    if visited[u] = 'G' then Exit(true); // Sąsiad szary - mamy cykl. przerywamy
    if (visited[u] = 'W') and
       isGraphCyclic(G,u,visited) then Exit(true); // Wywołanie rekurencyjne
    p := p^.next;
  end;
  visited[v] := 'B';             // Kolorujemy wierzchołek na czarno
  Exit(false);
end;

function isCyclic(n : integer; var G : Tlist) : boolean;
var
  i : integer;
  visited : array of char;
begin
  SetLength(visited,n);  // Tworzymy tablicę odwiedzin
  for i := 0 to n - 1 do
    visited[i] := 'W';   // Tablicę zerujemy
  for i := 0 to n - 1 do
    if (visited[i] = 'W') and
       isGraphCyclic(G,i,visited) then Exit(true);
  Exit(false);
end;

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

var
  n,m,i,v1,v2 : integer;
  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;
  end;

  if isCyclic(n,A) then writeln('CYCLIC GRAPH')
  else                  writeln('ACYCLIC GRAPH');

  // 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 cykliczności grafu skierowanego
// Data: 19.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa

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

// Funkcje badające cykliczność grafu
//-----------------------------------
bool isGraphCyclic(slistEl ** G, int v, char * visited)
{
  slistEl * p;                  // Wskaźnik elementu listy
  int u;

  visited[v] = 'G';             // Kolorujemy wierzchołek na szaro
  p = G[v];                     // Sprawdzamy kolejnych sąsiadów
  while(p)
  {
    u = p->v;                   // u <-- numer sąsiada
    if(visited[u] == 'G') return true; // Sąsiad szary - mamy cykl. przerywamy
    if((visited[u] == 'W') &&
       isGraphCyclic(G,u,visited)) return true; // Wywołanie rekurencyjne
    p = p->next;
  }
  visited[v] = 'B';             // Kolorujemy wierzchołek na czarno
  return false;
}

bool isCyclic(int n, slistEl ** G)
{
  int i;
  char * visited;

  visited = new char[n];        // Tworzymy tablicę odwiedzin
  for(i = 0; i < n; i++)
    visited[i] = 'W';           // Tablicę zerujemy
  for(i = 0; i < n; i++)
    if((visited[i] = 'W') &&
      isGraphCyclic(G,i,visited)) return true;
  return false;
}

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

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

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

  if(isCyclic(n,A)) cout << "CYCLIC GRAPH";
  else              cout << "ACYCLIC GRAPH";

  cout << endl;

  // 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 cykliczności grafu skierowanego
' Data: 19.12.2013
' (C)2013 mgr Jerzy Wałaszek
'----------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Funkcje badające cykliczność grafu
'-----------------------------------

Const WHITE = 0
Const GRAY = 1
Const BLACK = 2
 
Function isGraphCyclic(ByVal G As slistEl Ptr Ptr,_
	                    ByVal v As Integer, _
	                    ByVal visited As Byte Ptr) As Integer

  Dim As slistEl ptr p          ' Wskaźnik elementu listy
  Dim As Integer u

  visited[v] = GRAY             ' Kolorujemy wierzchołek na szaro
  p = G[v]                      ' Sprawdzamy kolejnych sąsiadów
  While p
    u = p->v                    ' u <-- numer sąsiada
    If visited[u] = GRAY Then Return 1 ' Sąsiad szary - mamy cykl. przerywamy
    If (visited[u] = WHITE) AndAlso _
       (isGraphCyclic(G,u,visited) = 1) Then Return 1 ' Wywołanie rekurencyjne
    p = p->Next
  Wend 
  visited[v] = BLACK            ' Kolorujemy wierzchołek na czarno
  Return 0
End Function

Function isCyclic(ByVal n As integer, ByVal G As slistEl Ptr Ptr) As Integer
  Dim As Integer i
  Dim As Byte Ptr visited

  visited = New Byte[n]         ' Tworzymy tablicę odwiedzin
  For i = 0 To n - 1
    visited[i] = WHITE           ' Tablicę zerujemy
  Next
  For i = 0 To n - 1
    If (visited[i] = WHITE) AndAlso _
       (isGraphCyclic(G,i,visited) = 1) Then Return 1
  Next
  Return 0
End Function

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

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

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
Next

Close #1

If isCyclic(n,A) Then
  Print "CYCLIC GRAPH"
Else
  Print "ACYCLIC GRAPH"
EndIf

' 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