//posl raskraska grafa s pomoshu
//modificirov spiskov smegnosti
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define XRY 8   //ko-vo vershin grafa
typedef int Boolean;
typedef struct zveno *svqz;
typedef struct zveno

{
  int Key;  // vershina
  svqz Up;  // ykazatel na smegnyu vershiny
  svqz Sled;// ykazat na sled smegnuy vershin

};

class Spisok
{
  private:
     svqz Beg[XRY+1]; //massiv ykazat na vershiny
     void Add_Ver (int);
     int Find (int, int, svqz *);
     void Add_duga (int, int);
     void Make (int, int);
     void Delinenok (int, int);
     void Del_Duga (int, int);
     void Del_Ver (int);
     int Find_Color (int, int, svqz *);
  public:
     Spisok();
     void Init_Graph ();
     void Make_Graph ();
     void Print_Graph ();
     void Color ();
     void Print_Color ();
};

void main ()
{char a;
FILE*f ;
clrscr();

printf("vvedite kol-vo stydentov");

fscanf(f," /d",&a);

  Spisok A;
  //inicializ grafa
  A.Init_Graph ();
  //postroenie grafa
  A.Make_Graph ();
  //vivod grafa
  A.Print_Graph ();
  getch();
  //posled raskraska grafa
  A.Color ();
  A.Print_Color ();
  getch();
}

Spisok::Spisok()
{
  for ( int i=0; i<=XRY;Beg[i++] = NULL );
}

void Spisok::Add_Ver (int x)
//fynciya sozdaniya vershiny X
{
  svqz Ukaz = new (zveno);

  Ukaz->Sled = NULL;
  Beg[x] = Ukaz;
}

void Spisok::Init_Graph ()
//fynkciya inizializaciivershin smegnosty
{
  for (int i=1;i<=XRY;i++) Add_Ver (i);
}

int Spisok::Find (int x, int y, svqz *UkZv)
//Fynciya proverki smegnosti vershiny i x.
//Ona vozvrashaet true, esli x smegna s y
// ykazatel *UkZv vozvrashaet ykazatel na mesto y
//v spiske smegnosti x. esli  vershina x ne smegna
// s y, to UkZv est null

{
  svqz Ukaz;

  Ukaz = Beg[x]->Sled;
  while  (Ukaz != NULL && Ukaz->Key != y)
     Ukaz = Ukaz->Sled;
  *UkZv = Ukaz;
  return  ( Ukaz != NULL );
}

void Spisok::Add_duga (int x, int y)
//fynkciya sozdaniya dygi (x,y).
{
  svqz Ukaz = new (zveno);

   Ukaz->Sled = Beg[x]->Sled; Ukaz->Key = y;
   Beg[x]->Sled = Ukaz;
}

void Spisok::Make (int x, int y)
//fynkciya sozdaniya rebra {x,y}.
{
  svqz Ukaz;

  if  ( !Find(x,y,&Ukaz) )
  {
     Add_duga (x,y);
     if ( x != y ) Add_duga (y,x);
     Beg[x]->Sled->Up = Beg[y];
     Beg[y]->Sled->Up = Beg[x];
  }
}

void Spisok::Make_Graph ()
//fink postroeniya modificirov spiskov smegnosti
{
  int f;

  for (int i=1;i<=XRY;i++)
  {
    cout << "Vvedite vershini, smegnie s " << i << "-i vershinoy: ";
    cin >> f;
    while (f!=0)
    {
      Make (i,f);
      cout << " ";
      cin >> f;
    }
    cout << endl;
  }
}

void Spisok::Delinenok (int x, int y)
//fynkciya ydaleniya dygi (x,y).
{
  svqz Ukaz;
  svqz Ukazlenok;

  Ukazlenok = Beg[x]; Ukaz = Beg[x]->Sled;
  while (Ukaz != NULL && Ukaz->Key != y)
  {  Ukazlenok = Ukaz; Ukaz = Ukaz->Sled; }
  if ( Ukaz != NULL )
  {
     Ukazlenok->Sled = Ukaz->Sled;
     delete Ukaz;
  }
}

void Spisok::Del_Duga (int x, int y)
//Fynkciya ydaleniya rebra {x,y}.
{
  Delinenok (x,y); Delinenok (y,x);
}

void Spisok::Del_Ver (int x)
//Fynkciya ydaleniya versh x.
{
  svqz Ukaz;
  svqz Ukazlenok;

  for (int i=1;i<=XRY;i++) Delinenok (i,x);
  Ukaz = Beg[x]; Beg[x] = NULL;
  while ( Ukaz != NULL )
  {
     Ukazlenok = Ukaz->Sled;
     delete Ukaz; Ukaz = Ukazlenok;
  }
}

void Spisok::Print_Graph ()
//fynk vivoda sodergimogo
//spiskov smegnosti
{
  svqz UkZv;

  for (int i=1;i<=XRY;i++)
  {
    if ( Beg[i] != NULL )
    {
      UkZv = Beg[i]->Sled;
      cout << i << " - ";
      while ( UkZv != NULL )
      {
	cout << " " << UkZv->Key;
	UkZv = UkZv->Sled;
      }
    }
    cout << endl;
  }
}

int Spisok::Find_Color (int x, int c, svqz *UkZv)
//Fynkciya viyavleniya vozmognosti raskraski vershiny x cvetom c
//fynk vorvrashaet true esli versh x mogno raskrasit
//ykazatel *UkZv vozvr ykazatel na versh smegnyu s x
//i raskrashennyu cvetom c. esli vershiny x mogno
//raskrasit, to *UkZv est null

{
   int i = 1;

   while (!(Find(x,i,&(*UkZv)) &&
	  Beg[i]->Key==c)   &&
	  i != x) i++;
   return (i==x);
}

void Spisok::Color ()
//fynkciya posledovatl raskraski grafa, zadannogo
//modificir spiskami smegnosti Beg
{
  int i = 1;
  int c = 1;
  svqz UkZv;

  while  (Beg[i] == NULL && i<=XRY) i++;
  if ( i != XRY )
  {
    Beg[i]->Key = c;
    i++;
    while  (i<=XRY)
     if ( Beg[i] != NULL )
     {
       c = 1;
       while  (!Find_Color(i,c,&UkZv)) c++;
       Beg[i]->Key = c; i++;
     }
     else  i++;
  }
  else  cout << "Graf otsytstvyet!";
}

void Spisok::Print_Color ()
//Fynkciya vivoda raskraskii grafa, zadannogo
//modificir spiskami smegnosti Beg
{
  for (int i=1;i<=XRY;i++)
    if ( Beg[i] != NULL )
       cout << " Color " << i << " - " << Beg[i]->Key << endl;
}