// Znajdowanie spójnych składowych
// Data: 27.08.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------

program spojsklad;

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

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

var
  n, m : integer;           // Liczba wierzchołków i krawędzi
  A   : TList;              // Tablica list sąsiedztwa
  C   : array of integer;   // Tablica z numerami spójnych składowych
  S   : stack;              // Stos
  cn, i, j, v, u : integer;
  p, r : PslistEl;

begin
  S.init;

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

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

  // Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

  for i := 0 to n - 1 do
  begin
    A [ 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 w
    p^.next := A [ v ];     // Dodajemy go na początek listy A [ v ] 
    A [ v ] := p;
    new ( p );              // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := A [ u ];
    A [ u ] := p;
  end;

  cn := 0;                  // Zerujemy licznik spójnych składowych

  for i := 0 to n-1 do
    if C [ i ] = 0 then     // Szukamy nieodwiedzonego jeszcze wierzchołka
    begin
      inc ( cn );           // Zwiększamy licznik składowych
      S.push ( i );         // Na stosie umieszczamy numer bieżącego wierzchołka
      C [ i ] := cn;        // Wierzchołek numerujemy i oznaczamy jako odwiedzony
      while not S.empty do  // Przechodzimy graf algorytmem DFS
      begin
        v := S.top;         // Pobieramy wierzchołek
        S.pop;              // Usuwamy go ze stosu
        p := A [ v ];       // Przeglądamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          u := p^.v;        // Numer sąsiada do u
          if C [ u ] = 0 then
          begin
            S.push ( u );   // Na stos idą sąsiedzi nieodwiedzeni
            C [ u ] := cn;  // i ponumerowani
          end;
          p := p^.next;
        end;
      end;
    end;

  writeln;

  for i := 1 to cn do
  begin
    write ( 'SCC ', i, ' : ' ); // Numer spójnej składowej
    for j := 0 to n-1 do
      if C [ j ] = i then write ( j:2, ' ' ); // Wierzchołki tej składowej
    writeln;
  end;

  writeln;

    // 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 );
  SetLength ( C, 0 );
  S.destroy;
end.

// Znajdowanie spójnych składowych
// Data: 27.08.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;
};

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

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

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

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

  A = new slistEl * [ n ]; // Tworzymy tablice dynamiczne
  C = new int [ n ];

  // Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

  for( i = 0; i < n; i++ )
  {
    A [ 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 slistEl;     // Tworzymy nowy element
    p->v = u;            // Numerujemy go jako w
    p->next = A [ v ];   // Dodajemy go na początek listy A [ v ] 
    A [ v ] = p;
    p = new slistEl;     // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = A [ u ];
    A [ u ] = p;
  }

  cn = 0;                 // Zerujemy licznik spójnych składowych

  for( i = 0; i < n; i++ )
    if( !C [ i ] )        // Szukamy nieodwiedzonego jeszcze wierzchołka
    {
      cn++;               // Zwiększamy licznik składowych
      S.push ( i );       // Na stosie umieszczamy numer bieżącego wierzchołka
      C [ i ] = cn;       // i oznaczamy go jako odwiedzonego i ponumerowanego
      while( !S.empty( ) ) // Przechodzimy graf algorytmem DFS
      {
        v = S.top( );     // Pobieramy wierzchołek
        S.pop( );         // Usuwamy go ze stosu

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

        for( p = A [ v ]; p; p = p->next )
        {
          u = p->v;       // Numer sąsiada do u
          if( !C [ u ] )
          {
            S.push ( u ); // Na stos idą sąsiedzi nieodwiedzeni
            C [ u ] = cn; // i ponumerowani
          }
        }
      }
    }

  for( i = 1; i <= cn; i++ )
  {
    cout << "SCC : " << i << ": "; // Numer spójnej składowej
    for( j = 0; j < n; j++ )
      if( C [ j ] == i ) cout << setw ( 2 ) << j << " "; // Wierzchołki tej składowej
    cout << endl;
  }

  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;
  delete [ ] C;

  return 0;
}

' Znajdowanie spójnych składowych
' Data: 27.08.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

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

Dim As Integer n, m       ' Liczba wierzchołków i krawędzi
Dim As slistEl Ptr Ptr A  ' Tablica list sąsiedztwa
Dim As Integer Ptr C      ' Tablica z numerami spójnych składowych
Dim As stack S            ' Stos
Dim As Integer cn, i, j, v, u
Dim As slistEl Ptr p, r

Open Cons For Input As #1

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

A = New slistEl Ptr [ n ] ' Tworzymy tablice dynamiczne
C = New Integer [ n ] 

' Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

For i = 0 To n - 1
  A [ i ] = 0
  C [ i ] = 0
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 0 To m - 1
  Input #1, v, u          ' Wierzchołki tworzące krawędź
  p = new slistEl         ' Tworzymy nowy element
  p->v = u                ' Numerujemy go jako w
  p->next = A [ v ]       ' Dodajemy go na początek listy A [ v ] 
  A [ v ] = p
  p = new slistEl         ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = A [ u ] 
  A [ u ] = p
Next

cn = 0                    ' Zerujemy licznik spójnych składowych

For i = 0 To n - 1
  If C [ i ] = 0 Then     ' Szukamy nieodwiedzonego jeszcze wierzchołka
    cn += 1               ' Zwiększamy licznik składowych
    S.push ( i )          ' Na stosie umieszczamy numer bieżącego wierzchołka, 
    C [ i ] = cn          ' oznaczając go jako odwiedzonego i ponumerowanego
    While S.empty( ) = 0  ' Przechodzimy graf algorytmem DFS
      v = S.top( )        ' Pobieramy wierzchołek
      S.pop( )            ' Usuwamy go ze stosu
      p = A [ v ]         ' Przeglądamy sąsiadów wierzchołka v
      While p
        u = p->v          ' Numer sąsiada do u
        If C [ u ] = 0 Then
          S.push ( u )    ' Na stos idą sąsiedzi nieodwiedzeni
          C [ u ] = cn    ' i ponumerowani 
        End If
        p = p->next
      Wend
    Wend
  End If
Next

Print

For i = 1 To cn
  Print "SCC";i;":"; ' Numer spójnej składowej
  For j = 0 To n - 1
    If C [ j ] = i Then Print Using "###";j; ' Wierzchołki tej składowej
  Next
  Print
Next

Print

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

End

// Znajdowanie spójnych składowych
// za pomocą zbiorów rozłącznych
// Data: 1.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

// Typy danych dla drzew struktury zbiorów rozłącznych
type
  PTNode = ^TNode;
  TNode =  record
    up   : PTNode;                // Rodzic węzła
    rank : integer;               // Ranga
    data : integer;               // Zawartość węzła
  end;

// Tworzy drzewo jednowęzłowe
//---------------------------
procedure MakeSet ( x : PTNode );
begin
  x^.up := x;                     // x staje się korzeniem drzewa
  x^.rank := 0;                   // Rangę zerujemy
end;

// Zwraca korzeń drzewa i ustawia pola up
// wszystkich węzłów nadrzędnych aż do korzenia
//---------------------------------------------
function FindSet ( x : PTNode ) : PTNode;
begin
  if x^.up <> x then x^.up := FindSet ( x^.up );
  FindSet := x^.up;
end;

// Łączy ze sobą drzewa z x i z y
//-------------------------------
procedure UnionSets ( x, y : PTNode );
var
  rx, ry : PTNode;
begin
  rx := FindSet ( x );            // Wyznaczamy korzeń drzewa z węzłem x
  ry := FindSet ( y );            // Wyznaczamy korzeń drzewa z węzłem y
  if rx <> ry then                // Korzenie muszą być różne
  begin
    if rx^.rank > ry^.rank then   // Porównujemy rangi drzew
       ry^.up := rx               // rx większe, dołączamy ry
    else
    begin
      rx^.up := ry;               // równe lub ry większe, dołączamy rx
      if rx^.rank = ry^.rank then inc ( ry^.rank );
    end;
  end;
end;

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

var
  n, m : integer;                  // Liczba wierzchołków i krawędzi
  T   : array of TNode;
  i, j, v, u : integer;
begin
  read ( n, m );                   // Odczytujemy liczbę wierzchołków i krawędzi
  SetLength ( T, n );              // Ustalamy rozmiar tablicy zbiorów rozłącznych

  // Tablicę T inicjujemy

  for i := 0 to n - 1 do
  begin
    T [ i ].data := i;             // Numer węzła
    MakeSet ( addr ( T [ i ] ) );  // Tworzymy zbiór jednoelementowy
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m - 1 do
  begin
    read ( v, u );                    // Wierzchołki tworzące krawędź
    UnionSets ( addr ( T [ v ] ), addr ( T [ u ] ) ); // Łączymy zbiory z u i v
  end;

  // Wypisujemy wyniki

  writeln;

  for i := 0 to n - 1 do
    if i = FindSet ( addr ( T [ i ] ))^.data then
    begin
      write ( 'SCC id =', i:3, ' : ' );
      for j := 0 to n - 1 do
        if i = FindSet ( addr ( T [ j ] ))^.data then write ( j:3 );
      writeln;
    end;

  // Usuwamy tablicę zbiorów rozłącznych

  SetLength ( T, 0 );

end.

// Znajdowanie spójnych składowych
// za pomocą zbiorów rozłącznych
// Data: 1.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych dla drzew struktury zbiorów rozłącznych

struct TNode
{
  TNode *up;                // Rodzic węzła
  int rank;                 // Ranga
  int data;                 // Zawartość węzła
};

// Tworzy drzewo jednowęzłowe
//---------------------------
void MakeSet ( TNode * x )
{
  x->up = x;                // x staje się korzeniem drzewa
  x->rank = 0;              // Rangę zerujemy
}

// Zwraca korzeń drzewa i ustawia pola up
// wszystkich węzłów nadrzędnych aż do korzenia
//---------------------------------------------
TNode * FindSet ( TNode * x )
{
  if( x->up != x ) x->up = FindSet ( x->up );
  return x->up;
}

// Łączy ze sobą drzewa z x i z y
//-------------------------------
void UnionSets ( TNode *x, TNode *y )
{
  TNode *rx, *ry;

  rx = FindSet ( x );       // Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet ( y );       // Wyznaczamy korzeń drzewa z węzłem y
  if( rx != ry )            // Korzenie muszą być różne
  {
    if( rx->rank > ry->rank ) // Porównujemy rangi drzew
       ry->up = rx;         // rx większe, dołączamy ry
    else
    {
      rx->up = ry;          // równe lub ry większe, dołączamy rx
      if( rx->rank == ry->rank ) ry->rank++;
    }
  }
}

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

int main( )
{
  int n, m;                 // Liczba wierzchołków i krawędzi
  TNode * T;
  int i, j, v, u;

  cin >> n >> m;            // Odczytujemy liczbę wierzchołków i krawędzi
  T = new TNode [ n ];      // Tworzymy tablicę zbiorów rozłącznych

  // Tablicę T inicjujemy

  for( i = 0; i < n; i++ )
  {
    T [ i ].data = i;       // Numer węzła
    MakeSet ( &T [ i ] );   // Tworzymy zbiór jednoelementowy
  }

  // Odczytujemy kolejne definicje krawędzi.

  for( i = 0; i < m; i++ )
  {
    cin >> v >> u;          // Wierzchołki tworzące krawędź
    UnionSets ( &T [ v ], &T [ u ] ); // Łączymy zbiory z u i v
  }

  // Wypisujemy wyniki

  cout << endl;

  for( i = 0; i < n; i++ )
    if( i == FindSet ( &T [ i ] )->data )
    {
      cout << "SCC id =" << setw ( 3 ) << i << ":";
      for( j = 0; j < n; j++ )
        if( i == FindSet ( &T [ j ] )->data ) cout << setw ( 3 ) << j;
      cout << endl;
    }

  // Usuwamy tablicę zbiorów rozłącznych

  delete [ ] T;

  return 0;
}

' Znajdowanie spójnych składowych
' za pomocą zbiorów rozłącznych
' Data: 1.04.2014
' (C)2014 mgr Jerzy Wałaszek
'--------------------------------

' Typy danych dla drzew struktury zbiorów rozłącznych

Type TNode
  up As TNode Ptr                 ' Rodzic węzła
  rank As Integer                 ' Ranga
  Data As Integer                 ' Zawartość węzła
End Type

' Tworzy drzewo jednowęzłowe
'---------------------------
Sub MakeSet ( ByVal x As TNode Ptr )
  x->up = x                       ' x staje się korzeniem drzewa
  x->rank = 0                     ' Rangę zerujemy  
End Sub

' Zwraca korzeń drzewa i ustawia pola up
' wszystkich węzłów nadrzędnych aż do korzenia
'---------------------------------------------
Function FindSet ( ByVal x As TNode Ptr ) As TNode Ptr
  If x->up <> x Then x->up = FindSet ( x->up )
  return x->up
End Function

' Łączy ze sobą drzewa z x i z y
'--------------------------------
Sub UnionSets ( ByVal x As TNode Ptr, ByVal y As TNode Ptr )

  Dim As TNode Ptr rx, ry

  rx = FindSet ( x )             ' Wyznaczamy korzeń drzewa z węzłem x
  ry = FindSet ( y )             ' Wyznaczamy korzeń drzewa z węzłem y
  If rx <> ry Then               ' Korzenie muszą być różne
    If rx->rank > ry->rank Then  ' Porównujemy rangi drzew
      ry->up = rx                ' rx większe, dołączamy ry
    Else
      rx->up = ry                ' równe lub ry większe, dołączamy rx
      If rx->rank = ry->rank Then ry->rank += 1
    End If
  End If
End Sub

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

Dim As Integer n, m             ' Liczba wierzchołków i krawędzi
Dim As TNode Ptr T
Dim As integer i, j, v, u

Open Cons For Input As #1

Input #1, n, m                  ' Odczytujemy liczbę wierzchołków i krawędzi
T = New TNode [ n ]             ' Tworzymy tablicę zbiorów rozłącznych

' Tablicę T inicjujemy

For i = 0 To n - 1
  T [ i ].data = i               ' Numer węzła
  MakeSet ( VarPtr ( T [ i ] ) ) ' Tworzymy zbiór jednoelementowy
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 0 To m - 1
  Input #1, v, u           ' Wierzchołki tworzące krawędź
  UnionSets ( VarPtr ( T [ v ] ), VarPtr ( T [ u ] ) ) ' Łączymy zbiory z u i v
Next

Close #1

' Wypisujemy wyniki

Print

For i = 0 To n - 1
  If i = FindSet ( VarPtr ( T [ i ] ) )->Data Then
    Print Using "SCC id =### :";i;
    For j = 0 To n - 1
      If i = FindSet ( VarPtr ( T [ j ] ) )->Data Then Print Using "###";j;
    Next
    Print
  End If
Next

' Usuwamy tablicę zbiorów rozłącznych

Delete [ ] T

End