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

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

class Spisok {
  private:
    Lref Head; //Указатель на список заголовочных узлов.
    Lref Tail; //Указатель на фиктивный элемент 
               //в конце списка заголовочных узлов.
    Lref SearchGraph(int);
    Lref Search(int);
  public:
    Spisok () {//Инициализация списка заголовочных узлов.
               Head = Tail = new (Leader); }
    ~Spisok(); //Деструктор.
    void MakeGraph();
    void AddGraph(int, int);
    void DeleteGraph(int, int);
    void PrintGraph();
    void DeleteY(int);
    void Free1Graph(Lref *, Lref *);
    void Free2Graph(Tref *); 
};

void main ()
{
  Spisok A;
  int x,y; //Начало и конец дуги.

  //Построение и вывод структуры Вирта.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  cout<< "Добавим к графу новую дугу...\n";
  cout<< "Введите начало дуги: "; cin>>x;
  cout<< "Введите конец дуги: "; cin>>y;
  A.AddGraph (x,y);
  A.PrintGraph (); cout<<endl;
  cout<< "Добавим к графу новое ребро...\n";
  cout<< "Введите первую концевую вершину ребра: "; cin>>x;
  cout<< "Введите вторую концевую вершину ребра: "; cin>>y;
  A.AddGraph (x,y);
  A.AddGraph (y,x);
  A.PrintGraph (); cout<<endl;
  cout<< "Удалим из графа заданную дугу...\n";
  cout<< "Введите начало дуги: "; cin>>x;
  cout<< "Введите конец дуги: "; cin>>y;
  A.DeleteGraph (x,y);
  A.PrintGraph (); cout<<endl;
  cout<< "Удалим из графа заданное ребро...\n";
  cout<< "Введите первую концевую вершину ребра: "; cin>>x;
  cout<< "Введите вторую концевую вершину ребра: "; cin>>y;
  A.DeleteGraph (x,y);
  A.DeleteGraph (y,x);
  A.PrintGraph (); cout<<endl;
  cout<< "Введите удаляемую вершину: "; cin>>y;
  A.DeleteY (y);
  A.PrintGraph (); cout<<endl;
}

Spisok::~Spisok()
{
  //Очистка структуры Вирта.
  Lref t = Head;
  while (t!=Tail)
  { Free2Graph (&(*t).Trail); t = (*t).Next; }
  Free1Graph (&Head,&Tail);
  delete Tail;
}

Lref Spisok::SearchGraph (int w)
//Функция возвращает указатель на заголовочный узел 
//с ключом w. Если заголовочный узел отсутствует, то он 
//добавляется в список. Head - указатель на структуру Вирта.
{
  Lref h;

  h = Head; (*Tail).Key = w;
  while ((*h).Key!=w) h = (*h).Next;
  if (h==Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
  { Tail = new (Leader); (*h).Count = 0; 
    (*h).Trail = NULL; (*h).Next = Tail; }
  return h;
}

Lref Spisok::Search (int w)
//Функция возвращает указатель на заголовочный узел 
//ключом w. Если узел отсутствует, то функция возвращает NULL .
{
  Lref h = Head;
  (*Tail).Key = w; //Поиск "с барьером".
  while ((*h).Key!=w) h = (*h).Next;
  if (h==Tail) //В списке заголовочных узлов нет узла с ключом w.
    h = NULL;
  return h;
} 

void Spisok::MakeGraph ()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
  int x,y;
  Lref p,q;    //Рабочие указатели.
  Tref t,r;    // Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.

  cout<<"Вводите начальную вершину дуги: ";
  cin>>x;
  while (x!=0)
  {
    cout<<"Вводите конечную вершину дуги: "; cin>>y;
    //Определим, существует ли в графе дуга (x,y)?
    p=SearchGraph (x); q=SearchGraph (y);
    r = (*p).Trail; Res = FALSE; 
    while ((r!=NULL)&&(!Res)) 
      if ((*r).Id==q) Res = TRUE; 
      else r = (*r).Next; 
    if (!Res) //Если дуга отсутствует, то поместим её в граф.
    { t = new (Trailer); (*t).Id = q; 
      (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; } 
    cout<<"Вводите начальную вершину дуги: "; cin>>x;
  }
}

void Spisok::AddGraph (int x,int y)
//Добавление дуги (x,y) (если ее не было!) к структуре
//Вирта, соответствующей ориентированному графу Head.
{
  Lref p,q;    //Рабочие указатели.
  Tref t,r;    //Рабочие указатели.
  Boolean Res; //Флаг наличия в графе данной дуги.

  //Определим, существует ли в графе дуга (x,y)? 
  p=SearchGraph (x); q=SearchGraph (y);
  r = (*p).Trail; Res = FALSE;
  while ((r!=NULL)&&(!Res)) 
    if ((*r).Id==q) Res = TRUE; else r = (*r).Next;
  if (!Res)
  { //Если дуга отсутствует, то поместим её в граф.
    t = new (Trailer); (*t).Id = q; (*t).Next = (*p).Trail; 
    (*p).Trail = t; (*q).Count++;
  }
} 

void Spisok::DeleteGraph (int x,int y)
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу
//и полученную удалением дуги (x,y).
{
  Lref p,q;    //Рабочие указатели.
  Tref t,r;    //Рабочие указатели.
  Boolean Res; //Флаг наличия в графе данной дуги.

  //Определим, существует ли в графе дуга (x,y)?
  p=Search (x); q= Search (y);
  if ((p!=NULL)&&(q!=NULL))
  { //Вершины x и y в графе есть.
    r = (*p).Trail; Res = FALSE; 
    while ((r!=NULL)&&(!Res)) 
      if ((*r).Id==q) Res = TRUE; 
      else r = (*r).Next; 
   if (Res) //Если дуга существует, то удалим её.
   if (r==(*p).Trail)
     { (*p).Trail = (*(*p).Trail).Next; delete r; (*q).Count--; } 
   else 
    {
      t = (*p).Trail; 
      while ((*t).Next!=r) t = (*t).Next;
      (*t).Next = (*(*t).Next).Next; delete r; (*q).Count--; }
    }
} 

void Spisok::PrintGraph ()
//Вывод структуры Вирта, заданной указателем 
//Head и соответствующей ориентированному графу.
{
  Lref p; //Рабочий указатель.
  Tref q; //Рабочий указатель.

  p = Head;
  while (p!=Tail)
  {
    cout<<"("<<(*p).Key; q = (*p).Trail; 
    while (q!=NULL) 
    { cout<<(*(*q).Id).Key; q = (*q).Next; } 
    cout<<")"; p = (*p).Next; cout<<" ";
  }
}

void Spisok::DeleteY (int y)
//Функция возвращает указатель Head на структуру Вирта, 
//соответствующую графу с удаленной вершиной y.
{ 
  Lref p,q; //Рабочие указатели.
  Tref r,s; //Рабочие указатели.
  int x;    //Рабочая переменная.
  //Удаление всех дуг (x,y), оканчивающихся  в вершине y.
  p = Head; 
  while (p!=Tail) 
  { x = (*p).Key; DeleteGraph (x,y); p = (*p).Next; } 
  //Удаление списка смежности вершины y.
  p=SearchGraph (y); r = (*p).Trail;
  while (r!=NULL) 
  { s = r; r = (*r).Next; (*(*s).Id).Count++; delete s; } 
  //Удаление узла, содержащего вершину y, из  списка заголовочных узлов.
  q = Head; 
  if (q==p) { Head = (*Head).Next; delete q; } 
  else { 
    while ((*q).Next!=p) q = (*q).Next; 
    (*q).Next = (*p).Next; delete p; }
} 

void Spisok::Free1Graph (Lref *Head, Lref *Tail)
//Очистка динамической памяти, занятой линейным списком, 
// заданным указателем *Head.
{
  if (*Head!=*Tail)
  { Free1Graph (&(**Head).Next,Tail); delete *Head; *Head = NULL; }
} 

void Spisok::Free2Graph (Tref *X)
//Очистка динамической памяти, занятой линейным списком, 
// заданным указателем *X.
{
  if (*X!=NULL)
  { Free2Graph (&(**X).Next); delete *X; *X = NULL; }
}