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

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

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

int VspomSet[256]; // Множество, содержащее вершины графа,
                   // имеющие нулевое количество предшественников.
                   // По умолчанию элементы инициалируются 0.

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

int Spisok::Vyvod()
{
  Lref p,q; // Рабочие указатели.
  Tref t;
  
  cout << "\nРезультат топологической сортировки:\n";
  q = Head;
  while ( q!=NULL) 
  {
     cout << q->Key << " "; VspomSet[q->Key] = 1;
     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";
      return 1;
    }
  else return 0;
}

void Spisok::Neupor()
{
  Lref p,q,r; // Рабочие указатели.
  Tref t;
  int Flag;

  cout << "Имеется следующий контур (контур печатается ";
  cout << "в обратном порядке):\n";
  //В дальнейшем работаем только с копией основного списка.
  p = Head;
  while (p!=Tail)
  {
    if ( VspomSet[p->Key] ) p->Trail = NULL;
    p = p->Next;
  }
  // ------- 
  p = Head;
  while ( p!=Tail ) 
  { p->Count = 0; p = p->Next; }
  // --------------------------------------- 
  p = Head;
  while ( p!=Tail )
  {
    r = p; t = p->Trail; p->Trail = NULL;
    while ( t!=NULL )
    {
      if  (t!=NULL && t->Id->Count==0) t->Id->Count = r->Key;
      t = t->Next;
    }
    p = p->Next;
  }
  // ---------------------- 
  p = Head; Flag = FALSE;
  while (p!=Tail && !Flag) 
    if ( p->Count!=0 ) Flag = TRUE;
    else  p = p->Next;
  // --------------------------------------- 
  t = new (Trailer); // Создали вспомогательную запись.
A: 
  p->Trail = t;
  q = Head; Flag = FALSE;
  while  (q!=Tail && !Flag)
    if ( q->Key==p->Count ) Flag = TRUE;
    else  q = q->Next;
  if ( q->Trail==NULL ) { p = q; goto A; }
  // ----------------------------------- 
  z = p->Key; // Сохранили начало контура.
B: 
  cout << p->Key << " ";
  p->Trail = NULL;
  q = Head; Flag = FALSE;
  while  (q!=Tail && !Flag)
   if ( q->Key==p->Count ) Flag = TRUE;
   else  q = q->Next;
  if ( q->Trail!=NULL ) { p = q; goto B; }
  cout << z; // Напечатали начало контура.
}

void main()
{
  Spisok A,A_Copy;
  Lref p,q; // Рабочие указатели.
  Tref t;
  Lref p1,q1; // Рабочие указатели для создания копии списка.
  Tref t1;
  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;
    //Построение копии основного списка.
    p1 = A_Copy.L(x); q1 = A_Copy.L(y);
    t1 = new (Trailer); t1->Id = q1; t1->Next = p1->Trail;
    p1->Trail = t1; q1->Count += 1;
    cout << "Элемент "; 
    cin >> x;
    cout << " предшествует элементу ";
  }
  // Поиск ведущих с нулевым количеством предшественников.
  A.Poisk();
  // Фаза вывода.
  if (A.Vyvod()) //Если множество неупорядоченное, 
                 //то работаем с копией.
       A_Copy.Neupor();
}