// Sortowanie topologiczne
// Data: 13.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program tsort;

// Typy danych

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

  PDLel = ^DLel;
  DLel =  record
    prev, next : PDLel;
    v          : integer;
  end;

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

var
  n, m, i, v1, v2 : integer;
  ps, rs   : PSLel;
  pd, rd, L : PDLel;
  graf    : array of PSLel;
  Vind    : array of integer;
  test    : boolean;

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

  // Tworzymy tablice dynamiczne

  SetLength (graf, n);
  for i := 0 to n-1 do graf [i] := nil;

  // Odczytujemy definicje krawędzi grafu

  for i := 0 to m-1 do
  begin
    read (v1, v2);
    new (ps);
    ps^.v := v2;
    ps^.next := graf [v1];
    graf [v1] := ps;
  end;

  writeln;

  // Wykonujemy sortowanie topologiczne grafu

  SetLength (Vind, n);      // Tworzymy tablicę stopni wchodzących
  for i := 0 to n-1 do Vind [i] := 0; // Zerujemy tablicę Vind []

  for i := 0 to n-1 do      // Przeglądamy graf
  begin
    ps := graf [i];         // Przeglądamy sąsiadów każdego wierzchołka
    while ps <> nil do
    begin
      inc (Vind [ps^.v]); // Wyznaczamy ich stopnie wchodzące
      ps := ps^.next;         // Następny sąsiad
    end;
  end;

  L := nil;
  for i := n-1 downto 0 do  // Na liście L umieszczamy od 0 do n-1
  begin
    new (pd);
    pd^.v := i;
    pd^.next := L;
    if pd^.next <> nil then pd^.next^.prev := pd;
    pd^.prev := nil;
    L := pd;
  end;

  repeat
    test := false;            // Oznaczamy brak usunięcia wierzchołka

    pd := L;                  // Przeglądamy listę L
    while pd <> nil do

      if Vind [pd^.v] > 0 then pd := pd^.next // Wierzchołki o niezerowym stopniu wchodzącym pomijamy
      else
      begin
        test := true;         // Będzie usunięcie wierzchołka
        ps := graf [pd^.v]; // Przeglądamy listę sąsiadów
        while ps <> nil do
        begin
          dec (Vind [ps^.v]); // Modyfikujemy ich stopnie wchodzące
          ps := ps^.next;     // Następny sąsiad
        end;

        write (pd^.v, ' '); // Wypisujemy usuwany wierzchołek
        rd := pd;             // Zapamiętujemy adres elementu L
        pd := pd^.next;       // Następny wierzchołek na liście lub nil!

        // Zapamiętany element rd listy L usuwamy z pamięci

        if rd^.next <> nil then rd^.next^.prev := rd^.prev;
        if rd^.prev <> nil then rd^.prev^.next := rd^.next
        else L := pd;
        dispose (rd);
      end;

   until not test;

  writeln; writeln;

  // Usuwamy zmienne dynamiczne

  SetLength (Vind, 0);

  for i := 0 to n-1 do
  begin
    ps := graf [i];
    while ps <> nil do
    begin
      rs := ps;
      ps := ps^.next;
      dispose (rs);
    end;
  end;
  SetLength (graf, 0);

  pd := L;
  while pd <> nil do
  begin
    rd := pd;
    pd := pd^.next;
    dispose (rd);
  end;
end.

// Sortowanie topologiczne
// Data: 13.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Typy danych

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

struct DLel
{
  DLel *prev, *next;
  int v;
};

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

int main()
{
  int n, m, i, v1, v2, *Vind;
  SLel *ps, *rs, **graf;
  DLel *pd, *rd, *L;
  bool test;

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

  // Tworzymy tablice dynamiczne

  graf = new SLel * [n];
  for(i = 0; i < n; i++) graf [i] = NULL;

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    ps = new SLel;
    ps->v = v2;
    ps->next = graf [v1];
    graf [v1] = ps;
  }

  cout << endl;

  // Wykonujemy sortowanie topologiczne grafu

  Vind = new int [n];         // Tworzymy tablicę stopni wchodzących
  for(i = 0; i < n; i++) Vind [i] = 0; // Zerujemy tablicę Vind []

  for(i = 0; i < n; i++)      // Przeglądamy graf
    for(ps = graf [i];ps;ps = ps->next) // Przeglądamy sąsiadów każdego wierzchołka
      Vind [ps->v] ++;        // Wyznaczamy ich stopnie wchodzące

  L = NULL;
  for(i = n-1; i >= 0; i--) // Na liście L umieszczamy od 0 do n-1
  {
    pd = new DLel;
    pd->v = i;
    pd->next = L;
    if(pd->next) pd->next->prev = pd;
    pd->prev = NULL;
    L = pd;
  }

  do
  {
    test = false;             // Oznaczamy brak usunięcia wierzchołka

    pd = L;                   // Przeglądamy listę L
    while(pd)
      if(Vind [pd->v]) pd = pd->next; // Wierzchołki o niezerowym stopniu wchodzącym pomijamy
      else
      {
        test = true;          // Będzie usunięcie wierzchołka
        for(ps = graf [pd->v];ps;ps = ps->next) // Przeglądamy listę sąsiadów
          Vind [ps->v] --;  // Modyfikujemy ich stopnie wchodzące

        cout << pd->v << " "; // Wypisujemy usuwany wierzchołek
        rd = pd;              // Zapamiętujemy adres elementu L
        pd = pd->next;        // Następny wierzchołek na liście lub NULL!

        // Zapamiętany element rd listy L usuwamy z pamięci

        if(rd->next) rd->next->prev = rd->prev;
        if(rd->prev) rd->prev->next = rd->next;
        else L = pd;
        delete rd;
      }
  } while(test);

  cout << endl << endl;

  // Usuwamy zmienne dynamiczne

  delete [] Vind;

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

  pd = L;
  while(pd)
  {
    rd = pd;
    pd = pd->next;
    delete rd;
  }

  return 0;}

' Sortowanie topologiczne
' Data: 13.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych

Type SLel
  Dim As SLel Ptr Next
  Dim As Integer v
End Type

Type DLel
  Dim As DLel Ptr prev, Next
  Dim As Integer v
End Type

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

Dim As Integer n, m, i, v1, v2
Dim As Integer Ptr Vind
Dim As SLel Ptr ps, rs
Dim As SLel Ptr Ptr graf
Dim As DLel Ptr pd, rd, L
Dim As Byte test

Open Cons For Input As #1

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

' Tworzymy tablice dynamiczne

graf = New SLel Ptr [n]
For i = 0 To n-1: graf [i] = 0: Next

' Odczytujemy definicje krawędzi grafu

For i = 0 To m-1
  Input #1, v1, v2
  ps = New SLel
  ps->v = v2
  ps->next = graf [v1]
  graf [v1] = ps
Next

Close #1

Print

' Wykonujemy sortowanie topologiczne grafu

Vind = new integer [n]    ' Tworzymy tablicę stopni wchodzących
For i = 0 To n-1
  Vind [i] = 0            ' Zerujemy tablicę Vind []
Next

For i = 0 To n-1          ' Przeglądamy graf
  ps = graf [i]
  While ps                  ' Przeglądamy sąsiadów każdego wierzchołka
    Vind [ps->v] += 1     ' Wyznaczamy ich stopnie wchodzące
    ps = ps->Next           ' Następny sąsiad
  Wend
Next 

L = 0
For i = n-1 To 0 Step -1  ' Na liście L umieszczamy od 0 do n-1
  pd = New DLel
  pd->v = i
  pd->next = L
  If pd->Next Then pd->next->prev = pd
  pd->prev = 0
  L = pd
Next

Do
  test = 0                  ' Oznaczamy brak usunięcia wierzchołka

  pd = L                    ' Przeglądamy listę L
  While pd
    If Vind [pd->v] > 0 Then
    	pd = pd->Next ' Wierzchołki o niezerowym stopniu wchodzącym pomijamy
    Else
      test = 1              ' Będzie usunięcie wierzchołka
      ps = graf [pd->v]
      While ps              ' Przeglądamy listę sąsiadów
        Vind [ps->v] -= 1 ' Modyfikujemy ich stopnie wchodzące
        ps = ps->Next       ' Następny sąsiad
      Wend
      print pd->v;          ' Wypisujemy usuwany wierzchołek
      rd = pd               ' Zapamiętujemy adres elementu L
      pd = pd->Next         ' Następny wierzchołek na liście lub 0!

     ' Zapamiętany element rd listy L usuwamy z pamięci

     If rd->Next then rd->next->prev = rd->prev
     If rd->prev Then
     	 rd->prev->next = rd->Next
     Else
       L = pd
     End If

     Delete rd
    End If
  Wend
Loop While test = 1

Print
Print

' Usuwamy zmienne dynamiczne

Delete [] Vind

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

Delete [] graf

pd = L
While pd
  rd = pd
  pd = pd->Next
  Delete rd
Wend

End

// Sortowanie topologiczne z DFS
// Data: 14.02.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

program tsort;

// Typy danych

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

// Zmienne globalne
//-----------------
var
  sptr : integer;
  graf : array of PSLel;
  visited : array of byte;
  S : array of integer;

const
  WHITE = 0;                     // kolory wierzchołków
  GRAY  = 1;
  GREEN = 2;

// Rekurencyjna funkcja dokonująca sortowania topologicznego
// v-wierzchołek startowy
//----------------------------------------------------------
function DFStsort (v : integer) : boolean;
var
  p : PSLel;
begin
  if visited [v] = GRAY then   // Sprawdzamy, czy nie ma cyklu
  begin
    writeln;                     // Jest cykl-sortowanie topologiczne
    writeln('NOT A DAG');     // nie może zostać wykonane
    writeln;
    Exit (false);
  end;
  if visited [v] = WHITE then  // Jeśli wierzchołek jest biały, 
  begin
    visited [v] := GRAY;       // to kolorujemy go na szaro
    p := graf [v];             // i przeglądamy wszystkich sąsiadów
    while p <> nil do
    begin
      if not DFStsort (p^.v) then Exit (false); // Wywołanie rekurencyjne
      p := p^.next;              // Następny sąsiad
    end;
    visited [v] := GREEN;      // Wierzchołek kolorujemy na zielono
    S [sptr] := v;             // i umieszczamy go na stosie
    inc (sptr);
  end;
  DFStsort := true;              // Kończymy z wynikiem true
end;

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

var
  n, m, i, v1, v2 : integer;
  p, r : PSLel;

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

  // Tworzymy tablice dynamiczne

  SetLength (graf, n);
  SetLength (S, n); sptr := 0; // Pusty stos
  SetLength (visited, n);
  for i := 0 to n-1 do
  begin
    graf [i] := nil;
    visited [i] := WHITE;      // Wierzchołki kolorujemy na biało
  end;

  // Odczytujemy definicje krawędzi grafu

  for i := 0 to m-1 do
  begin
    read (v1, v2);
    new (p);
    p^.v := v2;
    p^.next := graf [v1];
    graf [v1] := p;
  end;

  writeln;

  // Wykonujemy sortowanie topologiczne grafu

  for i := 0 to n-1 do
    if visited [i] = WHITE then
    begin
      if not DFStsort (i) then break;
    end;

  // Wypisujemy wyniki

  if sptr = n then
    for i := n-1 downto 0 do write (S [i], ' ');

  writeln;

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

// Sortowanie topologiczne z DFS
// Data: 14.02.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Typy danych

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

// Zmienne globalne
//-----------------
int sptr, *S;
SLel **graf;
char *visited;

const char WHITE = 0;             // kolory wierzchołków
const char GRAY  = 1;
const char GREEN = 2;

// Rekurencyjna funkcja dokonująca sortowania topologicznego
// v-wierzchołek startowy
//----------------------------------------------------------
bool DFStsort (int v)
{
  SLel *p;

  if(visited [v] == GRAY)     // Sprawdzamy, czy nie ma cyklu
  {
    cout << "\nNOT A DAG\n\n";    // Jest cykl-sortowanie topologiczne
    return false;                 // nie może zostać wykonane
  }
  if(visited [v] == WHITE)    // Jeśli wierzchołek jest biały, 
  {
    visited [v] = GRAY;         // to kolorujemy go na szaro
    for(p = graf [v];p;p = p->next) // i przeglądamy wszystkich sąsiadów
      if(!DFStsort (p->v)) return false; // Wywołanie rekurencyjne
    visited [v] = GREEN;        // Wierzchołek kolorujemy na zielono
    S [sptr++] = v;             // i umieszczamy go na stosie
  }
  return true;                    // Kończymy z wynikiem true
}

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

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

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

  // Tworzymy tablice dynamiczne

  graf = new SLel * [n];
  S    = new int [n]; sptr = 0; // Pusty stos
  visited = new char [n];
  for(i = 0; i < n; i++)
  {
    graf [i] = NULL;
    visited [i] = WHITE;        // Wierzchołki kolorujemy na biało
  }

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    p = new SLel;
    p->v = v2;
    p->next = graf [v1];
    graf [v1] = p;
  }

  cout << endl;

  // Wykonujemy sortowanie topologiczne grafu

  for(i = 0; i < n; i++)
    if(visited [i] == WHITE)
    {
      if(!DFStsort (i)) break;
    }

  // Wypisujemy wyniki

  if(sptr == n)
    for(i = n-1; i >= 0; i--) cout << S [i] << " ";

  cout << endl;

  // Usuwamy zmienne dynamiczne

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

  return 0;}

' Sortowanie topologiczne z DFS
' Data: 14.02.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------

' Typy danych

Type SLel
  Dim As SLel Ptr Next
  Dim As Integer v
End Type

' Zmienne globalne
'-----------------

Dim Shared As Integer sptr
Dim Shared As Integer Ptr S
Dim Shared As SLel Ptr Ptr graf
Dim Shared As Byte Ptr visited

const WHITE = 0           ' kolory wierzchołków
const GRAY  = 1
const GREEN = 2

' Rekurencyjna funkcja dokonująca sortowania topologicznego
' v-wierzchołek startowy
'----------------------------------------------------------
Function DFStsort (ByVal v As Integer) As Integer
  Dim As SLel Ptr p

  If visited [v] = GRAY Then ' Sprawdzamy, czy nie ma cyklu
    Print                    ' Jest cykl-sortowanie topologiczne
    Print "NOT A DAG"        ' nie może zostać wykonane
    Print
    Return 0
  End If
 
  If visited [v] = WHITE Then ' Jeśli wierzchołek jest biały, 
    visited [v] = GRAY     ' to kolorujemy go na szaro
    p = graf [v]
    While p                  ' i przeglądamy wszystkich sąsiadów
      If DFStsort (p->v) = 0 Then return 0 ' Wywołanie rekurencyjne
      p = p->Next            ' Następny sąsiad
    Wend
    visited [v] = GREEN    ' Wierzchołek kolorujemy na zielono
    S [sptr] = v           ' i umieszczamy go na stosie
    sptr += 1
  End If
  return 1                   ' Kończymy z wynikiem true
End Function

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

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

Open Cons For Input As #1
Input #1, n, m               ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy tablice dynamiczne

graf = New SLel Ptr [n]
S    = New integer [n]     ' Pusty stos
sptr = 0
visited = New Byte [n]
For i = 0 To n-1
  graf [i] = 0
  visited [i] = WHITE      ' Wierzchołki kolorujemy na biało
Next

' Odczytujemy definicje krawędzi grafu

For i = 0 To m-1
  Input #1, v1, v2
  p = New SLel
  p->v = v2
  p->next = graf [v1]
  graf [v1] = p
Next

Print

' Wykonujemy sortowanie topologiczne grafu

For i = 0 To n-1
  If visited [i] = WHITE Then
    If DFStsort (i) = 0 Then Exit For
  End If
Next

' Wypisujemy wyniki

If sptr = n Then
  For i = n-1 To 0 Step -1
  	 Print S [i];
  Next
End If

Print

' Usuwamy zmienne dynamiczne

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

End