#include <iostream.h>
typedef struct Leader  *Lref; //Тип: указатель на заголовочный узел.
typedef struct Trailer *Tref; //Тип: указатель на дуговой узел.
//Описание типа заголовочного узла.
typedef struct Leader 
{
  int Key;    //Информационное поле.
  int Count;  //Количество предшественников.
  int CountF; //Количество последователей.
  Tref Trail; 
  Lref Next;  
};

//Описание типа дугового узла.
typedef struct Trailer 
{
  Lref Id; 
  Tref Next; 
};

class Spisok {
  private:
    Lref Head; //Указатель на список заголовочных узлов.
    Lref Tail; //Указатель на фиктивный элемент 
               //в конце списка заголовочных узлов.
    int z;     //Количество узлов, не имеющих предшественников.
    int  Length_List(Tref);
    void Sorting (Lref);
  public:
    Spisok () {//Инициализация списка заголовочных узлов.
               Head = Tail = new (Leader); z = 0;};
    Lref L (int); 
    void Poisk();
    void Vyvod();
    void Zapoln();
};

void Spisok::Zapoln()
// Заполнение полей CountF узлов построенного графа.
{ 
  Lref p; // Рабочий указатель.

  p = Head;
  while ( p!=Tail)
  {
    p->CountF = Length_List (p->Trail);
    p = p->Next;
  }
}

void Spisok::Poisk()
{
  Lref p,q; // Рабочие указатели.
  
  p = Head; Head = NULL;
  while (p!=Tail)
  {
     q = p; p = p->Next;
     if (q->Count==0)
       { q->Next = Head; Head = q; }
   }
}

Lref Spisok::L (int w) 
//Функция возвращает указатель на ведущего с ключом w.
{
  Lref h = Head;

  Tail->Key = w;
  while (h->Key!=w) h = h->Next;
  if (h==Tail)
  // В списке нет элемента с ключом w.
  {
    Tail = new (Leader); z++;
    h->Count = 0; h->Trail = NULL; h->Next = Tail;
  }
  return h;
}

void Spisok::Vyvod()
{
  Lref p,q; // Рабочие указатели.
  Tref t;
  
  cout << "\nРезультат топологической сортировки:\n";
  q = Head;
  while ( q!=NULL) 
  {
     Sorting (q);
     cout << q->Key << " "; 
     z--;
     t = q->Trail; q = q->Next;
     while (t!=NULL)
     {
       p = t->Id; p->Count--;
       if  (p->Count==0) // Включение (*p) в список ведущих.
         { p->Next = q; q = p; }
       t = t->Next;
     }
  }
  if (z!=0)
      cout << "\nМножество не является частично упорядоченным!\n";
}

int Spisok::Length_List (Tref T)
// Функция позволяет найти количество элементов в линейном списке.
// T - указатель на звено, следующее за заглавным звеном.
{
  if (T==NULL) return 0;
  else  return 1 + Length_List(T->Next);
}

void Spisok::Sorting (Lref Head)
// Сортировка списка элементов по полю CountF
// в порядке убывания.
// 21.10.93 (c) Коврижных Д. & Швецкий М.В.
{
  Lref UkZv_1,UkZv_2;
  int A,B,C;
  Tref D;
  Lref UkZv_3; // Рабочий указатель.
  Tref UkZv_4; // Рабочий указатель.

  UkZv_1 = Head;
  while ( UkZv_1!=NULL )
  {
     UkZv_2 = UkZv_1->Next;
     while  (UkZv_2!=NULL)
     {
       if  (UkZv_1->CountF < UkZv_2->CountF)
         {
           A              = UkZv_1->Key;
           B              = UkZv_1->Count;
           C              = UkZv_1->CountF;
           D              = UkZv_1->Trail;

           UkZv_1->Key    = UkZv_2->Key;
           UkZv_1->Count  = UkZv_2->Count;
           UkZv_1->CountF = UkZv_2->CountF;
           UkZv_1->Trail  = UkZv_2->Trail;

           UkZv_2->Key    = A;
           UkZv_2->Count  = B;
           UkZv_2->CountF = C;
           UkZv_2->Trail  = D;

           UkZv_3 = Head;
           while  (UkZv_3!=NULL)
           {
              UkZv_4 = UkZv_3->Trail;
              while  (UkZv_4!=NULL)
              {
                 if  (UkZv_4->Id==UkZv_1)
                      UkZv_4->Id = UkZv_2;
                 else
                   if ( UkZv_4->Id==UkZv_2 ) UkZv_4->Id = UkZv_1;
                 UkZv_4 = UkZv_4->Next;
              }
              UkZv_3 = UkZv_3->Next;
           }
         }
       UkZv_2 = UkZv_2->Next;
     }
     UkZv_1 = UkZv_1->Next;
  }
}

void main()
{
  Spisok A;
  Lref p,q; // Рабочие указатели.
  Tref t;
  int  x,y; // Рабочие переменные.

  // Фаза ввода.
  cout << "Задайте отношение частичного порядка...\n";
  cout << "Элемент "; 
  cin >> x; 
  cout << " предшествует элементу ";
  while (x!=0)
  {
    cin >> y;
    p = A.L(x); q = A.L(y);
    t = new (Trailer); t->Id = q; t->Next = p->Trail;
    p->Trail = t; q->Count += 1;
    cout << "Элемент "; 
    cin >> x;
    cout << " предшествует элементу ";
  }
  // Заполнение полей CountF узлов построенного графа.
  A.Zapoln();
  // Поиск ведущих с нулевым количеством предшественников.
  A.Poisk();
  // Фаза вывода.
  A.Vyvod();
}