// Wyznaczanie silnie spójnych składowych
// Data: 18.01.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;

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, czy istnieje ścieżka od u do v
// u   -wierzchołek startowy ścieżki
// v   -wierzchołek końcowy ścieżki
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// Wynik:
// true-istnieje ścieżka od u do v
// false- nie istnieje ścieżka od u do v
//----------------------------------------------
function DFSback (u, v, n : integer; var graf : TList) : boolean;
var
  i, x, y   : integer;
  S       : Stack;
  visited : array of boolean;
  p       : PSLel;
begin
  SetLength (visited, n);      // Tworzymy tablicę odwiedzin
  for i := 0 to n-1 do         // i wypełniamy ją wartościami false
    visited [i] := false;

  S.init;                        // Tworzymy stos
  S.push (u);                  // Wierzchołek startowy na stos
  visited [u] := true;         // Oznaczamy go jako odwiedzonego

  while not S.empty do           // Uruchamiamy przejście DFS
  begin
    x := S.top;                  // Pobieramy wierzchołek ze stosu
    S.pop;                       // Pobrany wierzchołek usuwamy ze stosu

    p := graf [x];                // Przeglądamy sąsiadów
    while p <> nil do
    begin
      y := p^.v;                 // Numer sąsiada do y
      if y = v then              // Jeśli sąsiadem jest wierzchołek v, 
      begin                      // to ścieżka znaleziona
        S.destroy;               // Zerujemy stos
        SetLength (visited, 0); // Usuwamy tablicę visited
        Exit (true);           // Kończymy z wynikiem true
      end;
      if not visited [y] then
      begin
        S.push (y);            // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited [y] := true;   // i oznaczamy jako odwiedzonego
      end;
      p := p^.next;              // Następny sąsiad
    end;
  end;

  SetLength (visited, 0);      // Usuwamy tablicę visited
  DFSback := false;              // i kończymy z wynikiem false
end;

// Procedura przechodzi przez graf od wierzchołka startowego v
// i umieszcza w tablicy C informację o przynależności wierzchołków
// do określonej silnie spójnej składowej.
// v   -wierzchołek startowy
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// cn  -numer silnie spójnej składowej
// C   -tablica numerów silnie spójnych składowych dla wierzchołków
// Wynik:
// Ustawia tablicę C
//--------------------------------------------------------------------
procedure DFSscc (v, n : integer; var graf : TList;
                 cn  : integer; var C : array of integer);
var
  i, u, w   : integer;
  S       : Stack;
  visited : array of boolean;
  p       : PSLel;
begin
  SetLength (visited, n);
  for i := 0 to n-1 do visited [i] := false;

  S.init;

  S.push (v);                // Wierzchołek startowy na stos
  visited [v] := true;       // Oznaczamy go jako odwiedzonego
  C [v] := cn;               // Ustawiamy dla v numer składowej

  while not S.empty do         // Przejście DFS
  begin
    u := S.top;                // Odczytujemy wierzchołek ze stosu
    S.pop;                     // Usuwamy ze stosu odczytany wierzchołek

    if(u <> v) and DFSback (u, v, n, graf) then C [u] := cn;

    p := graf [u];           // Przeglądamy sąsiadów wierzchołka u
    while p <> nil do
    begin
      w := p^.v;
      if not visited [w] then
      begin
        S.push (w);          // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited [w] := true; // i oznaczamy jako odwiedzonego
      end;
      p := p^.next;            // Następny sąsiad
    end;
  end;

  SetLength (visited, 0);
end;

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

var
  n, m      : integer;         // Liczba wierzchołków i krawędzi
  graf     : TList;            // Tablica list sąsiedztwa grafu
  C        : array of integer; // Tablica numerów składowych
  i, v, u, cn : integer;
  p, r      : PSLel;

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

  SetLength (graf, n);   // Tworzymy tablice dynamiczne
  SetLength (C, n);

  // Inicjujemy tablice

  for i := 0 to n-1 do
  begin
    graf [i] := nil;
    C [i]    := 0;
  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;

  // Wyznaczamy silnie spójne składowe

  cn := 0;                   // Inicjujemy licznik składowych

  for v := 0 to n-1 do     // Przeglądamy kolejne wierzchołki grafu
    if C [v] = 0 then
    begin
      inc (cn);
      DFSscc (v, n, graf, cn, C); // Wyznaczamy silnie spójną składową
    end;

  // Wyświetlamy silnie spójne składowe

  writeln;

  for i := 1 to cn do
  begin
    write ('SCC', i:3, ' :');
    for v := 0 to n-1 do
      if C [v] = i then write (v:3);
    writeln;
  end;

  writeln;

  // Usuwamy tablice 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 (C, 0);

end.

// Wyznaczanie silnie spójnych składowych
// Data: 18.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

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, czy istnieje ścieżka od u do v
// u   -wierzchołek startowy ścieżki
// v   -wierzchołek końcowy ścieżki
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// Wynik:
// true-istnieje ścieżka od u do v
// false- nie istnieje ścieżka od u do v
//----------------------------------------------
bool DFSback (int u, int v, int n, SLel ** graf)
{
  int i, x, y;
  Stack S;
  bool * visited;
  SLel * p;

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

  S.push (u);               // Wierzchołek startowy na stos
  visited [u] = true;       // Oznaczamy go jako odwiedzonego

  while(!S.empty())        // Uruchamiamy przejście DFS
  {
    x = S.top();             // Pobieramy wierzchołek ze stosu
    S.pop();                 // Pobrany wierzchołek usuwamy ze stosu

    for(p = graf [x]; p; p = p->next) // Przeglądamy sąsiadów
    {
      y = p->v;               // Numer sąsiada do y
      if(y == v)            // Jeśli sąsiadem jest wierzchołek v, 
      {                       // to ścieżka znaleziona
        delete [] visited;   // Usuwamy tablicę visited
        return true;          // Kończymy z wynikiem true
      }
      if(!visited [y])
      {
        S.push (y);         // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited [y] = true; // i oznaczamy jako odwiedzonego
      }
    }
  }

  delete [] visited;         // Usuwamy tablicę visited
  return false;               // i kończymy z wynikiem false
}

// Procedura przechodzi przez graf od wierzchołka startowego v
// i umieszcza w tablicy C informację o przynależności wierzchołków
// do określonej silnie spójnej składowej.
// v   -wierzchołek startowy
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// cn  -numer silnie spójnej składowej
// C   -tablica numerów silnie spójnych składowych dla wierzchołków
// Wynik:
// Ustawia tablicę C
//--------------------------------------------------------------------
void DFSscc (int v, int n, SLel ** graf, int cn, int * C)
{
  int i, u, w;
  Stack S;
  bool * visited;
  SLel * p;

  visited = new bool [n];
  for(i = 0; i < n; i++) visited [i] = false;

  S.push (v);                // Wierzchołek startowy na stos
  visited [v] = true;        // Oznaczamy go jako odwiedzonego
  C [v] = cn;                // Ustawiamy dla v numer składowej

  while(!S.empty())         // Przejście DFS
  {
    u = S.top();              // Odczytujemy wierzchołek ze stosu
    S.pop();                  // Usuwamy ze stosu odczytany wierzchołek

    if((u != v) && DFSback (u, v, n, graf)) C [u] = cn;

    for(p = graf [u]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka u
    {
      w = p->v;
      if(!visited [w])
      {
        S.push (w);          // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited [w] = true;  // i oznaczamy jako odwiedzonego
      }
    }
  }

  delete [] visited;
}

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

int main()
{
  int n, m;                  // Liczba wierzchołków i krawędzi
  SLel ** graf;           // Tablica list sąsiedztwa
  int * C;                   // Tablica z numerami spójnych składowych
  int i, v, u, cn;
  SLel *p, *r;

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

  graf = new SLel * [n]; // Tworzymy tablice dynamiczne
  C = new int [n];

  // Inicjujemy tablice

  for(i = 0; i < n; i++)
  {
    graf [i] = NULL;
    C [i] = 0;
  }

  // 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 w
    p->next = graf [v];    // Dodajemy go na początek listy graf [v]
    graf [v] = p;
  }

  // Wyznaczamy silnie spójne składowe

  cn = 0;                    // Inicjujemy licznik składowych

  for(v = 0; v <= n-1; v++) // Przeglądamy kolejne wierzchołki grafu
    if(!C [v]) DFSscc (v, n, graf, ++cn, C); // Wyznaczamy silnie spójną składową


  // Wyświetlamy silnie spójne składowe

  cout << endl;

  for(i = 1; i <= cn; i++)
  {
    cout << "SCC" << setw (3) << i << ":";
    for(v = 0; v < n; v++) if(C [v] == i) cout << setw (3) << v;
    cout << endl;
  }

  cout << endl;

  // Usuwamy tablice dynamiczne

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

  return 0;}

' Wyznaczanie silnie spójnych składowych
' Data: 18.01.2014
' (C)2014 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, czy istnieje ścieżka od u do v
' u   -wierzchołek startowy ścieżki
' v   -wierzchołek końcowy ścieżki
' n   -liczba wierzchołków w grafie
' graf-tablica list sąsiedztwa
' Wynik:
' 1   -istnieje ścieżka od u do v
' 0   -nie istnieje ścieżka od u do v
'----------------------------------------------
Function DFSback (ByVal u As Integer, ByVal v As integer, ByVal n As integer, _
	             ByVal graf As SLel Ptr Ptr) As Integer
  Dim As integer i, x, y
  Dim As Stack S
  Dim As Byte Ptr visited
  Dim As SLel Ptr  p

  visited = New Byte [n]  ' Tworzymy tablicę odwiedzin
  For i = 0 To n-1        ' i wypełniamy ją wartościami false
    visited [i] = 0
  Next

  S.push (u)              ' Wierzchołek startowy na stos
  visited [u] = 1         ' Oznaczamy go jako odwiedzonego

  While S.empty() = 0      ' Uruchamiamy przejście DFS
    x = S.top()            ' Pobieramy wierzchołek ze stosu
    S.pop()                ' Pobrany wierzchołek usuwamy ze stosu

    p = graf [x]
    While p                 ' Przeglądamy sąsiadów
      y = p->v              ' Numer sąsiada do y
      If y = v Then         ' Jeśli sąsiadem jest wierzchołek v, to ścieżka znaleziona
        Delete [] visited  ' Usuwamy tablicę visited
        return 1            ' Kończymy z wynikiem true
      End If
     
      If visited [y] = 0 Then
        S.push (y)        ' Nieodwiedzonego sąsiada umieszczamy na stosie
        visited [y] = 1   ' i oznaczamy jako odwiedzonego
      End If
      p = p->Next           ' Następny sąsiad
    Wend
  Wend

  Delete [] visited        ' Usuwamy tablicę visited
  Return 0                  ' i kończymy z wynikiem false
End Function

' Procedura przechodzi przez graf od wierzchołka startowego v
' i umieszcza w tablicy C informację o przynależności wierzchołków
' do określonej silnie spójnej składowej.
' v   -wierzchołek startowy
' n   -liczba wierzchołków w grafie
' graf-tablica list sąsiedztwa
' cn  -numer silnie spójnej składowej
' C   -tablica numerów silnie spójnych składowych dla wierzchołków
' Wynik:
' Ustawia tablicę C
'--------------------------------------------------------------------
Sub DFSscc (ByVal v As integer, ByVal n As integer, _
             ByVal graf As SLel Ptr ptr, _
	       ByVal cn As integer, ByVal C As Integer Ptr)

  Dim As Integer i, u, w
  Dim As Stack S
  Dim As Byte Ptr visited
  Dim As SLel Ptr p

  visited = New Byte [n]
  For i = 0 To n-1
  	 visited [i] = 0
  Next

  S.push (v)               ' Wierzchołek startowy na stos
  visited [v] = 1          ' Oznaczamy go jako odwiedzonego
  C [v] = cn               ' Ustawiamy dla v numer składowej
 
  While S.empty() = 0       ' Przejście DFS
    u = S.top()             ' Odczytujemy wierzchołek ze stosu
    S.pop()                 ' Usuwamy ze stosu odczytany wierzchołek

    if(u <> v) AndAlso (DFSback (u, v, n, graf) = 1) Then C [u] = cn                 

    p = graf [u]
    While p                  ' Przeglądamy sąsiadów wierzchołka u
      w = p->v
      If visited [w] = 0 Then
        S.push (w)         ' Nieodwiedzonego sąsiada umieszczamy na stosie
        visited [w] = 1    ' i oznaczamy jako odwiedzonego
      End If
      p = p->Next
    Wend
  Wend

  Delete [] visited
End Sub

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

Dim As Integer n, m          ' Liczba wierzchołków i krawędzi
Dim As SLel Ptr Ptr graf  ' Tablica list sąsiedztwa grafu
Dim As Integer Ptr C
Dim As Integer i, v, u, cn
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
C = New Integer [n]

' Inicjujemy tablice

For i = 0 To n-1
  graf [i] = 0
  C [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

' Wyznaczamy silnie spójne składowe

cn = 0                    ' Inicjujemy licznik składowych

For v = 0 To n-1        ' Przeglądamy kolejne wierzchołki grafu
  If C [v] = 0 Then
  	  cn += 1
  	  DFSscc (v, n, graf, cn, C) ' Wyznaczamy silnie spójną składową
  EndIf
Next

' Wyświetlamy silnie spójne składowe

Print

For i = 1 To cn
  Print Using "SCC### :"; i;
  For v = 0 To n-1
    If C [v] = i Then Print Using "###";v;
  Next
  Print
Next

Print

' 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 [] C

End

// Wyznaczanie silnie spójnych składowych
// Algorytm Tarjana
// Data: 2.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program scc;

// Typy danych
type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

// Typ danych dla listy silnie spójnych składowych
  PsSLel = ^sSLel;
  sSLel = record
    next : PsSLel;
    v    : PSLel;
  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  : array of integer;
  VS       : array of boolean;
  S        : Stack;
  graf     : array of PSLel;
  Lscc     : PsSLel;

// 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ą.
// v-wierzchołek startowy dla DFS
//---------------------------------------------------
procedure DFSscc (v : integer);
var
  u : integer;
  sccp, p : PSLel;
  listp  : PsSLel;
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
    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
    sccp := nil;             // Dodajemy tę składową do listy składowych
    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
      new (p);             // Nowy element listy wierzchołków
      p^.v := u;             // Zapisujemy w nim wierzchołek
      p^.next := sccp;       // dodajemy go na początek listy
      sccp := p;
    until u = v;             // Kontynuujemy aż do korzenia składowej

    new (listp);           // Nowy element listy składowych
    listp^.v := sccp;        // Zapisujemy w nim listę
    listp^.next := Lscc;     // i dołączamy na początek listy składowych
    Lscc := listp;
  end;
end;

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

var
  i, v, u      : integer;
  p, r        : PSLel;
  listp, listr: PsSLel;

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 (VLow, n);
  SetLength (VS, n);

  // Inicjujemy tablice

  for i := 0 to n-1 do
  begin
    graf [i] := nil;
    VN [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;

  // Wyznaczamy silnie spójne składowe

  cvn := 0;                  // Zerujemy numer wierzchołka

  Lscc := nil;               // Tworzymy pustą listę składowych

  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

  listp := Lscc;             // Przeglądamy listę składowych
  cvn := 0;                  // cvn jest teraz licznikiem składowych
  while listp <> nil do
  begin
    inc (cvn);             // Zwiększamy numer składowej
    write ('SCC', cvn:3, ' :'); // Wyświetlamy numer składowej
    p := listp^.v;           // Przeglądamy listę wierzchołków
    while p <> nil do
    begin
      write (p^.v:3);      // Wyświetlamy wierzchołek składowej
      p := p^.next;          // Następny wierzchołek na liście
    end;
    writeln;
    listp := listp^.next;    // Następna składowa na liście
  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;

  listp := Lscc;
  while listp <> nil do
  begin
    p := listp^.v;
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
    listr := listp;
    listp := listp^.next;
    dispose (listr);
  end;

  SetLength (graf, 0);
  SetLength (VN, 0);
  SetLength (VLow, 0);
  SetLength (VS, 0);

  S.destroy;
end.

// Wyznaczanie silnie spójnych składowych
// Algorytm Tarjana
// Data: 2.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

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

// Typ danych dla listy silnie spójnych składowych

struct sSLel
{
  sSLel * next;
  SLel  * 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);
};

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

int      n, m, cvn, *VN, *VLow;
bool     *VS;
Stack    S;
SLel  **graf;
sSLel *Lscc;

//---------------------
// 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ą.
// v-wierzchołek startowy dla DFS
//---------------------------------------------------
void DFSscc (int v)
{
  int u;
  SLel  *sccp, *p;
  sSLel *listp;

  VN [v] = VLow [v] = ++cvn;  // Numerujemy wierzchołek i ustawiamy 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
    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ą
  {
    sccp = NULL;                  // Dodajemy tę składową do listy składowych
    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
      p = new SLel;            // Nowy element listy wierzchołków
      p->v = u;                   // Zapisujemy w nim wierzchołek
      p->next = sccp;             // dodajemy go na początek listy
      sccp = p;
    } while(u != v);            // Kontynuujemy aż do korzenia składowej

    listp = new sSLel;         // Nowy element listy składowych
    listp->v = sccp;              // Zapisujemy w nim listę
    listp->next = Lscc;           // i dołączamy na początek listy składowych
    Lscc = listp;
  }
}

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

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

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

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

  // Inicjujemy tablice

  for(i = 0; i < n; i++)
  {
    graf [i] = NULL;
    VN [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;

  // Wyznaczamy silnie spójne składowe

  cvn = 0;                        // Zerujemy numer wierzchołka

  Lscc = NULL;                    // Tworzymy pustą listę składowych

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

  cvn = 0;                        // cvn jest teraz licznikiem składowych
  for(listp = Lscc;listp;listp = listp->next) // Przeglądamy listę składowych
  {
    cout << "SCC" << setw (3) << ++cvn << ":"; // Wyświetlamy numer składowej
    for(p = listp->v;p;p = p->next) // Przeglądamy listę wierzchołków
      cout << setw (3) << p->v; // Wyświetlamy wierzchołek składowej
    cout << endl;
  }

  // Usuwamy zmienne dynamiczne

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

  listp = Lscc;
  while(listp)
  {
    p = listp->v;
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
    listr = listp;
    listp = listp->next;
    delete listr;
  }

  delete [] graf;
  delete [] VN;
  delete [] VLow;
  delete [] VS;

  return 0;}

' Wyznaczanie silnie spójnych składowych
' Algorytm Tarjana
' Data: 2.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy danych

Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type sSLel
  next As sSLel Ptr
  v As SLel Ptr
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
Dim Shared As Byte Ptr VS
Dim Shared As Stack S
Dim Shared As SLel Ptr Ptr graf
Dim Shared As sSLel Ptr Lscc

'---------------------
' 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ą.
' v-wierzchołek startowy dla DFS
'---------------------------------------------------
Sub DFSscc (ByVal v As Integer)
  Dim As Integer u
  Dim As SLel Ptr sccp, p
  Dim As sSLel Ptr listp

  cvn += 1                      ' Zwiększamy bieżący numer wierzchołka
  VN [v] = cvn                ' Numerujemy wierzchołek
  VLow [v] = cvn              ' i ustawiamy 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
    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ą
    sccp = 0                    ' Dodajemy tę składową do listy składowych
    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
      p = new SLel           ' Nowy element listy wierzchołków
      p->v = u                  ' Zapisujemy w nim wierzchołek
      p->next = sccp            ' dodajemy go na początek listy
      sccp = p
    Loop While u <> v           ' Kontynuujemy aż do korzenia składowej

    listp = new sSLel        ' Nowy element listy składowych
    listp->v = sccp             ' Zapisujemy w nim listę
    listp->next = Lscc          ' i dołączamy na początek listy składowych
    Lscc = listp
  End If
End Sub

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

Dim As Integer i, v, u
Dim As SLel Ptr p, r
Dim As sSLel Ptr listp, listr

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]
VLow = New Integer [n]
VS   = New Byte [n]

' Inicjujemy tablice

For i = 0 To n-1
  graf [i] = 0
  VN [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

' Wyznaczamy silnie spójne składowe

cvn = 0                         ' Zerujemy numer wierzchołka

Lscc = 0                        ' Tworzymy pustą listę składowych

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

cvn = 0                         ' cvn jest teraz licznikiem składowych
listp = Lscc
While listp                     ' Przeglądamy listę składowych
  cvn += 1
  Print Using "SCC### :";cvn;   ' Wyświetlamy numer składowej
  p = listp->v
  While p                       ' Przeglądamy listę wierzchołków
    Print Using "###";p->v;     ' Wyświetlamy wierzchołek składowej
    p = p->Next                 ' Następny wierzchołek
  Wend 
  Print
  listp = listp->Next           ' Następna składowa
Wend

' Usuwamy tablice dynamiczne

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

listp = Lscc
While listp
  p = listp->v
  While p
    r = p
    p = p->Next
    Delete r
  Wend
  listr = listp
  listp = listp->Next
  Delete listr
Wend

Delete [] graf
Delete [] VN
Delete [] VLow
Delete [] VS

End