// DFS - szukanie ścieżki
// Data: 26.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bfs_path;

// Typy dla dynamicznej tablicy list sąsiedztwa i 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;

// Zmienne globalne
//-----------------
var
  n : integer;           // Liczba wierzchołków i krawędzi
  A : TList;             // Tablica list sąsiedztwa
  S       : stack;       // Stos
  visited : array of boolean; // Tablica odwiedzin
  vs, vk   : integer;    // Wierzchołki startowy i końcowy ścieżki

// Rekurencyjna funkcja DFS
//-------------------------
function DFS (v : integer) : boolean;
var
  p : PslistEl;
begin
  visited [v] := true; // Oznaczamy wierzchołek jako odwiedzony

  S.push (v);          // Zapamiętujemy wierzchołek na stosie

  if v = vk then exit (true); // Jeśli koniec, kończymy

  p := A [v];          // Przetwarzamy nieodwiedzonych sąsiadów
  while p <> nil do
  begin

    if(visited [p^.v] = false) and (DFS (p^.v) = true) then exit (true);

    p := p^.next;        // Następny sąsiad
  end;

  S.pop;                 // Brak ścieżki, usuwamy wierzchołek ze stosu
  exit (false);        // Kończymy z wynikiem false
end;

// Procedura szukania ścieżki
//---------------------------
procedure DFS_Path;
var
  i : integer;
begin
  SetLength (visited, n);  // Tworzymy tablice odwiedzin
  for i := 0 to n - 1 do // Tablicę visited zerujemy
    visited [i] := false;

  S.init;                // Inicjujemy stos

  if DFS (vs) = false then write ('BRAK')
  else
    while S.empty = false do // Wypisujemy ścieżkę
    begin
      write (S.top:3);
      S.pop;
    end;

  writeln;

  SetLength (visited, 0);
end;

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

var
  m, i : integer;
  p, r : PslistEl;

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 (vs, vk);     // Wierzchołek startowy i końcowy krawędzi
    new (p);           // Tworzymy nowy element
    p^.v := vk;          // Numerujemy go jako vk
    p^.next := A [vs]; // Dodajemy go na początek listy A [vs]
    A [vs] := p;
  end;

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  read (vs, vk);

  writeln;

  // Szukamy ścieżki

  DFS_Path;

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

  writeln;
end.

// DFS - szukanie ścieżki
// Data: 26.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu
//-----------------------------------------------------
struct slistEl
{
  slistEl * next;
  int v;
};

// Definicja typu obiektowego stack
//---------------------------------
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;
  }
}

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

int n;                   // Liczba wierzchołków
slistEl ** A;            // Macierz sąsiedztwa
stack S;                 // Stos
bool * visited;          // Tablica odwiedzin
int vs, vk;              // Wierzchołki startowy i końcowy ścieżki

// Rekurencyjna funkcja DFS
//-------------------------
bool DFS (int v)
{
  visited [v] = true;     // Oznaczamy wierzchołek jako odwiedzony

  S.push (v);             // Zapamiętujemy wierzchołek na stosie

  if(v == vk) return true; // Jeśli koniec, kończymy

  // Przetwarzamy nieodwiedzonych sąsiadów

  for(slistEl * p = A [v]; p; p = p->next)
    if(!visited [p->v] && DFS (p->v)) return true;

  S.pop();            // Brak ścieżki, usuwamy wierzchołek ze stosu
  return false;          // Kończymy z wynikiem false
}

// Procedura szukania ścieżki
//---------------------------
void DFS_Path()
{
  visited = new bool [n];// Tworzymy tablice odwiedzin
  for(int i = 0; i < n; i++) // Tablicę visited zerujemy
    visited [i] = false;

  if(!DFS (vs)) cout << "BRAK";
  else
    while(!S.empty())   // Wypisujemy ścieżkę
    {
      cout << setw (3) << S.top();
      S.pop();
    }

  cout << endl;

  delete [] visited;
}

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

int main()
{
  int m, i;
  slistEl *p, *r;

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

  A = new slistEl * [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 >> vs >> vk;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = vk;          // Numerujemy go jako vk
    p->next = A [vs]; // Dodajemy go na początek listy A [vs]
    A [vs] = p;
  }

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  cin >> vs >> vk;

  cout << endl;

  // Szukamy ścieżki

  DFS_Path();

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

  cout << endl;

  return 0;}

' DFS - szukanie ścieżki
' Data: 26.07.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

' Definicja typu obiektowego stack
'---------------------------------
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
  EndIf
End Sub

' Zmienne globalne
'-----------------
Dim Shared As Integer n         ' Liczba wierzchołków
Dim Shared As slistEl Ptr Ptr A ' Tablica list sąsiedztwa
Dim Shared As stack S           ' Stos
Dim Shared As Byte Ptr visited  ' Tablica odwiedzin
Dim Shared As Integer vs, vk    ' Wierzchołki startowy i końcowy ścieżki

' Rekurencyjna funkcja DFS
'-------------------------
Function DFS (byval v As Integer) As Integer

  Dim As slistEl Ptr p

  visited [v] = 1  ' Oznaczamy wierzchołek jako odwiedzony

  S.push (v)       ' Zapamiętujemy wierzchołek na stosie

  If v = vk Then return 1  ' Jeśli koniec, kończymy

  ' Przetwarzamy nieodwiedzonych sąsiadów

  p = A [v]
  While p
  	
    if(visited [p->v] = 0) AndAlso (DFS (p->v) = 1) Then Return 1
   
    p = p->Next
  Wend

  S.pop()  ' Brak ścieżki, usuwamy wierzchołek ze stosu
  return 0    ' Kończymy z wynikiem false
End Function

' Procedura szukania ścieżki
'---------------------------
Sub DFS_Path

  Dim i As Integer
 
  visited = new byte [n] ' Tworzymy tablice odwiedzin
  For i = 0 To n - 1       ' Tablicę visited zerujemy
    visited [i] = 0
  Next

  If DFS (vs) = 0 Then
  	 Print "BRAK";
  Else
    While S.empty() = 0 ' Wypisujemy ścieżkę
      Print Using "###";S.top;
      S.pop
    Wend
  End If
 
  Print

  Delete [] visited
End Sub

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

Dim As Integer m, i
Dim As slistEl Ptr p, r

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, vs, vk   ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl    ' Tworzymy nowy element
  p->v = vk          ' Numerujemy go jako vk
  p->next = A [vs] ' Dodajemy go na początek listy A [vs]
  A [vs] = p
Next

' Odczytujemy wierzchołek startowy i końcowy ścieżki

Input #1, vs, vk

Close #1

Print

DFS_Path  ' Szukamy ścieżki

' 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

Print

End

// BFS - szukanie ścieżki
// Data: 24.08.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bfs_path;

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

  TList = array of PslistEl;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

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

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push (v : integer);
var
  p : PslistEl;
begin
  new (p);
  p^.next := nil;
  p^.v := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose (p);
  end;
end;

// Zmienne globalne
//-----------------
var
  n : integer; // Liczba wierzchołków
  A : TList;   // Tablica list sąsiedztwa

// Procedura szukania ścieżki
// vs - numer wierzchołka startowego
// vk - numer wierzchołka końcowego
//----------------------------------
procedure BFS_Path (vs, vk : integer);
var
  Q       : queue;
  visited : array of boolean;
  P       : array of integer;
  v, u, i   : integer;
  pv      : PslistEl;
  found   : boolean;

begin
  Q.init;  // Inicjujemy kolejkę

  SetLength (visited, n); // Tworzymy tablice odwiedzin
  for i := 0 to n - 1 do // Tablicę visited zerujemy
    visited [i] := false;

  SetLength (P, n);  // Tworzymy tablicę ścieżki

  P [vs] := -1;

  Q.push (vs);       // W kolejce umieszczamy wierzchołek startowy

  visited [vs] := true; // i oznaczamy go jako odwiedzonego

  found := false;

  while Q.empty = false do
  begin
    v := Q.front;     // Pobieramy z kolejki wierzchołek v
    Q.pop;

    if v = vk then    // Sprawdzamy koniec ścieżki
    begin
      found := true;  // Zaznaczamy sukces
      break;          // Przerywamy pętlę
    end;

    pv := A [v];    // Przeglądamy sąsiadów wierzchołka v
    while pv <> nil do
    begin
      u := pv^.v;
      if visited [u] = false then
      begin
        P [u] := v; // W P zapisujemy fragment ścieżki
        Q.push (u); // Sąsiad zostaje umieszczony w kolejce
        visited [u] := true; // i oznaczony jako odwiedzony
      end;
      pv := pv^.next; // Następny sąsiad
    end;
  end;

  if found = false then write ('BRAK') // Ścieżka nie została znaleziona
  else
    while v > -1 do
    begin
      write (v:3); // Wypisujemy wierzchołki ścieżki
      v := P [v];  // Cofamy się do poprzedniego wierzchołka ścieżki
    end;

  SetLength (P, 0);
  SetLength (visited, 0);
  Q.destroy;         // Czyścimy kolejkę
end;

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

var
  m, i, v1, v2 : integer;
  p, r : PslistEl;

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;

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  read (v1, v2);

  writeln;

  BFS_Path (v1, v2);  // Szukamy ścieżki

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

  writeln;

end.

// BFS - szukanie ścieżki
// Data: 24.08.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

const int MAXINT = -2147483647;

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

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

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

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

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty (void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front (void)
{
  if(head) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push (int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop (void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

// Zmienne globalne
//-----------------
int n;        // Liczba wierzchołków
slistEl ** A; // Macierz sąsiedztwa

// Procedura szukania ścieżki
// vs - numer wierzchołka startowego
// vk - numer wierzchołka końcowego
//----------------------------------
void BFS_Path (int vs, int vk)
{
  queue Q;
  bool * visited, found;
  int  * P, v, u, i;
  slistEl * pv;

  visited = new bool [n]; // Tworzymy tablice odwiedzin
  for(i = 0; i < n; i++) // Tablicę visited zerujemy
    visited [i] = false;

  P = new int [n];       // Tworzymy tablicę ścieżki

  P [vs] = -1;

  Q.push (vs);           // W kolejce umieszczamy wierzchołek startowy

  visited [vs] = true;   // i oznaczamy go jako startowy

  found = false;

  while(!Q.empty())
  {
    v = Q.front();        // Pobieramy z kolejki wierzchołek v
    Q.pop();

    if(v == vk)          // Sprawdzamy koniec ścieżki
    {
      found = true;        // Zaznaczamy sukces
      break;               // Przerywamy pętlę
    }

    // Przeglądamy sąsiadów wierzchołka v

    for(pv = A [v]; pv; pv = pv->next)
    {
      u = pv->v;
      if(!visited [u])
      {
        P [u] = v;          // W P zapisujemy fragment ścieżki
        Q.push (u);         // Sąsiad zostaje umieszczony w kolejce
        visited [u] = true; // i oznaczony jako odwiedzony 
      }
    }
  }

  if(!found) cout << "BRAK";// Ścieżka nie została znaleziona
  else
    while(v > -1)
    {
      cout << setw (3) << v;// Wypisujemy wierzchołki ścieżki
      v = P [v];            // Cofamy się do poprzedniego wierzchołka ścieżki
    }

  delete [] P;
  delete [] visited;
}

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

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

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

  A = new slistEl * [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 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;
  }

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  cin >> v1 >> v2;

  cout << endl;

  BFS_Path (v1, v2); // Szukamy ścieżki

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

  cout << endl;

  return 0;}

' BFS - szukanie ścieżki
' Data: 24.08.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push (ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push (ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

' Zmienne globalne
'-----------------
Dim Shared As Integer n         ' Liczba wierzchołków
Dim Shared As slistEl Ptr Ptr A ' Tablica list sąsiedztwa

' Procedura szukania ścieżki
' vs - numer wierzchołka startowego
' vk - numer wierzchołka końcowego
'----------------------------------
Sub BFSPath (vs As integer, vk As integer)
	
  Dim As queue Q
  Dim As Byte Ptr visited
  Dim As Integer Ptr P
  Dim As Integer found, v, u, i
  Dim As slistEl Ptr pv

  visited = new Byte [n] ' Tworzymy tablice odwiedzin
  For i = 0 To n - 1       ' Tablicę visited zerujemy
    visited [i] = 0
  Next

  P = new Integer [n]    ' Tworzymy tablicę ścieżki

  P [vs] = -1

  Q.push (vs)            ' W kolejce umieszczamy wierzchołek startowy

  visited [vs] = 1       ' i oznaczamy go jako odwiedzonego

  found = 0

  While Q.empty() = 0

    v = Q.front()         ' Pobieramy z kolejki wierzchołek v
    Q.pop()

    If v = vk Then         ' Sprawdzamy koniec ścieżki
      found = 1            ' Zaznaczamy sukces
      Exit While           ' Przerywamy pętlę
    EndIf
     
    ' Przeglądamy sąsiadów wierzchołka v

    pv = A [v]
    While pv
      u = pv->v
      If visited [u] = 0 Then
        P [u] = v       ' W P zapisujemy fragment ścieżki
        Q.push (u)      ' Sąsiad zostaje umieszczony w kolejce
        visited [u] = 1 ' i oznaczony jako odwiedzony
      End If
      pv = pv->Next
    Wend
   
  Wend
 
  If found = 0 Then
  	  Print "BRAK"; ' Ścieżka nie została znaleziona
  Else
    While v > -1
      Print Using "###";v; ' Wypisujemy wierzchołki ścieżki
      v = P [v]     ' Cofamy się do poprzedniego wierzchołka ścieżki
    Wend
  EndIf

  Delete [] P
  Delete [] visited
End Sub

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

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

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

' Odczytujemy wierzchołek startowy i końcowy ścieżki

Input #1, v1, v2

Close #1

Print

BFSPath (v1, v2) ' Szukamy ścieżki

' 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