// Transpozycja grafu
// Data: 22.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program transg;

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

TList = array of PslistEl;

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

var
  n, m, v, u, i : integer; // Liczba wierzchołków i krawędzi
  A, AT      : TList;      // Tablice list sąsiedztwa grafu
  p, r       : PslistEl;

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

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

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    A [i]  := nil;
    AT [i] := nil;
  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 := A [v]; // i dodajemy na początek listy A [v]
    A [v] := p;
  end;

  // Wyznaczamy graf transponowany

  for v := 0 to n - 1 do      // Przeglądamy kolejne wierzchołki
  begin
    p := A [v];             // Przeglądamy sąsiadów v
    while p <> nil do
    begin
      new (r);                 // Tworzymy nowy element listy
      r^.v := v;              // Zapamiętujemy w nim wierzchołek v
      r^.next := AT [p^.v]; // i dodajemy do listy sąsiada
      AT [p^.v] := r;

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

  // Wypisujemy wyniki

  writeln;
  for v := 0 to n - 1 do
  begin
    write (v, ' :');
    p := AT [v];
    while p <> nil do
    begin
      write (' ', p^.v);
      p := p^.next;
    end;
    writeln;
  end;

  // Usuwamy tablice dynamiczne

  for i := 0 to n - 1 do
  begin
    p := A [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
    p := AT [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;

  SetLength (A, 0);
  SetLength (AT, 0);
end.

// Transpozycja grafu
// Data: 22.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa

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

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

int main()
{
  int n, m;                 // Liczba wierzchołków i krawędzi
  slistEl **A, **AT;        // Tablice list sąsiedztwa
  int i, v, u;
  slistEl *p, *r;

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

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

  // Inicjujemy tablice

  for(i = 0; i < n; i++) A [i] = AT [i] = NULL;

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

  // Wyznaczamy graf transponowany

  for(v = 0; v < n; v++)     // Przeglądamy kolejne wierzchołki
    for(p = A [v]; p; p = p->next) // Przeglądamy sąsiadów v
    {
      r = new slistEl;       // Tworzymy nowy element listy
      r->v = v;              // Zapamiętujemy w nim wierzchołek v
      r->next = AT [p->v]; // i dodajemy do listy sąsiada
      AT [p->v] = r;
    }

  // Wypisujemy wyniki

  cout << endl;
  for(v = 0; v < n; v++)
  {
    cout << v << ":";
    for(p = AT [v]; p; p = p->next) cout << " " << p->v;
    cout << endl;
  }

  // Usuwamy tablice dynamiczne

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

  return 0;}

' Transpozycja grafu
' Data: 22.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

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

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

' Inicjujemy tablice

For i = 0 To n - 1
  A [i]  = 0
  AT [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 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
Next

Close #1

' Wyznaczamy graf transponowany

For v = 0 To n - 1        ' Przeglądamy kolejne wierzchołki
  p = A [v]             ' Przeglądamy sąsiadów v
  While p
    r = New slistEl       ' Tworzymy nowy element listy
    r->v = v              ' Zapamiętujemy w nim wierzchołek v
    r->next = AT [p->v] ' i dodajemy do listy sąsiada
    AT [p->v] = r
    p = p->Next           ' Następny sąsiad
  Wend
Next

' Wypisujemy wyniki

Print
For v = 0 To n - 1
  Print v;":";
  p = AT [v]
  While p
    print p->v;
    p = p->Next
  Wend
  Print
Next
 
' Usuwamy tablice dynamiczne

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

Delete [] A
Delete [] AT

End