базисные циклы в графе. остова найдены!

// ConsoleApplicationOstov1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <windows.h>
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef struct L *Lref; // Тип: указатель на заголовочный узел.
typedef struct T *Tref; // Тип: указатель на дуговой узел.
 
using namespace std;
//Описание типа заголовочного узла.
typedef struct L 
{ 
  int Key; //Имя заголовочного узла.
  int Count; //Количество предшественников.
  Boolean Flag; //Флаг посещения узла при обходе.
  Tref Trail; //Указатель на список смежности.
  Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
} Leader;
 
//Описание типа дугового узла.
typedef struct T 
{ 
  Lref Id; 
  Tref Next; 
} Trailer;
 
//Описание типа узла стека.
typedef Tref TipElement;
typedef struct Zveno *svqz;
typedef struct Zveno 
{ 
  TipElement Element; //Указатель на список смежности.
  svqz Sled; 
} St;
 
class Spisok
{
  private:
    Lref Head; //Указатель на голову списка заголовочных узлов.
    Lref Tail; //Указатель на фиктивный элемент 
               // в конце списка заголовочных узлов.
    void SearchGraph (int, Lref *);
  public:
    Spisok() {//Инициализация списка заголовочных узлов.
              Head = Tail =  new (Leader); }
    Lref GetHead() { return Head; }
    Lref GetTail() { return Tail; }
    void MakeGraph ();
    void Ostov_Depth (Lref);
    void PrintGraph ();
};
 
void main ()
{
  setlocale(LC_ALL, "Russian");
  Spisok A;
  Lref t; //Рабочий указатель для перемещения 
          // по списку заголовочных звеньев.
  //Построение графа и вывод его структуры Вирта.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  //Построение стягивающего дерева (остова).
  cout<<"Остов: ";
  t = A.GetHead();
  while (t!=A.GetTail())
    { (*t).Flag = TRUE; t = (*t).Next; }
  A.Ostov_Depth (A.GetHead()); cout<<endl;
} 
 
void Spisok::SearchGraph (int w, Lref *h)
//Функция возвращает указатель на заголовочный узел 
//с ключом w в графе, заданном структурой Вирта с указателем Head. 
{
  *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; }
}
 
void Spisok::MakeGraph ()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
  setlocale(LC_ALL, "Russian");
  int x,y;
  Lref p,q; //Рабочие указатели.
  Tref t,r; //Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.
  cout<<"Вводите начальную вершину дуги: ";
  cin>>x;
  while (x!=0)
  {
     cout<<"Вводите конечную вершину дуги: "; cin>>y;
     //Определим, существует ли в графе дуга (x,y)?
     SearchGraph (x, &p); SearchGraph (y,&q);
     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::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::Ostov_Depth (Lref r)
//Рекурсивный обход графа в глубину, соединенный с
//нахождением ребра остовного дерева.
//r - указатель на структуру Вирта.
{
  Tref t;
  Lref s;
 
  s = r;
  t = (*r).Trail; (*r).Flag = FALSE;
  while (t!=NULL)
  { if ((*(*t).Id).Flag) 
    { cout << "(" << s->Key << "," << t->Id->Key << ") ";
      Ostov_Depth ((*t).Id);
    }
    t = (*t).Next; 
  }
}