#include <stdio.h>
#include <conio.h>
#include <stdlib.h>


/*------------------------------------------------------------------------
--------------------------------------------------------------------------*/
void ajout_arc(int **alpha, int **beta,int x, int y, int nbsommets, int nbarcs)
{
 int i, j;

 if (*beta==NULL)
 {
   *beta = (int *)malloc(sizeof(int));
   (*beta)[0]=y;
   for(i=0; i<nbsommets+1; i++)
   {
     if (i!=x)
       (*alpha)[i]=1;
     else
       (*alpha)[i]=0;
   }
 }
 else
 {
//   *nbarcs+=1;
   i=nbarcs;

   *beta=(int *)realloc(*beta, (i+1)*sizeof(int));

   while (i>(*alpha)[x])
   {
     (*beta)[i]=(*beta)[i-1];
     i--;
   }
   (*beta)[i]=y;
   for(i=x+1;i<nbsommets+1;i++)
     if ((*alpha)[i]>=x)
       (*alpha)[i]++;
 }
// alpha[nbsommets]=alpha[nbsommets-1];

}

/*------------------------------------------------------------------------
--------------------------------------------------------------------------*/
void supp_arc(int **alpha, int **beta,int x,int y, int nbsommets, int *nbarcs)
{
int i, j, k;

  j=(*alpha)[x];
  i=0;
  while (((*beta)[j+i]!=y) && (j+i<(*alpha)[x+1] ))
    i++;
  printf("i=%d j=%d valeur %d ", i, j, (*beta)[j+i]);

  if ((*beta)[j+i]==y)                // si trouv‚
  {                                   // on supprime
    printf("Trouv‚ : i=%d j=%d valeur %d ", i, j, (*beta)[j+i]);


    for(k=j+i; k<*nbarcs-1; k++)
      (*beta)[k]=(*beta)[k+1];

    (*nbarcs)--;
    *beta=(int *)realloc(*beta,*nbarcs);

    for(i=x+1;i<=nbsommets;i++)
      if ((*alpha[i]>=x))
	(*alpha)[i]--;
  }
  else printf("\nNon trouv‚");
}

/*------------------------------------------------------------------------
--------------------------------------------------------------------------*/
void saisie_graphe(int **alpha, int **beta,int *nbsommets, int *nbarcs)
{
int i, org, dest, arcs;

  // saisie du nombre de sommets
  printf("\nNombre de sommets dans le graphe : ");
  scanf("%d", nbsommets);

  *alpha=(int *)malloc((*nbsommets+1)*sizeof(int));
  for(i=0;i<*nbsommets+1;i++)
    (*alpha)[i]=0;

  // saisie du nombre d'arcs
  printf("Nombre d'arcs dans le graphe : ");
  scanf("%d", &arcs);

  *beta=NULL;
  *nbarcs=arcs;

  // saisie des arcs
  i=0;
  do
  {
    printf("Origine de l'arc nø%d : ",i);
    scanf("%d", &org);
    if (org<*nbsommets)
    {
      printf("Destination de l'arc nø%d : ",i);
      scanf("%d", &dest);
      if (dest<*nbsommets)
	ajout_arc(alpha, beta, org, dest, *nbsommets, *nbarcs);
      else
      {
	printf("Ce sommet n'existe pas");
	i--;
      }
    }
    else
    {
      printf("Ce sommet n'existe pas");
      i--;
    }
    i++;
  }while(i<*nbarcs);
}

/*------------------------------------------------------------------------
--------------------------------------------------------------------------*/
void affgraph(int *alpha, int *beta,int nbsommets, int nbarcs)
{
int i;

  printf("\ntableau beta :\n");
  for(i=0; i<nbarcs; i++)
    printf(" %3d ", beta[i]);

  printf("\ntableau alpha :\n");
  for(i=0; i<nbsommets+1; i++)
    printf(" %3d ", alpha[i]);

  getch();
}

/*------------------------------------------------------------------------
--------------------------------------------------------------------------*/
void main(void)
{
int nbsommets, nbarcs;
int *alpha, *beta;

  clrscr();
  saisie_graphe(&alpha, &beta, &nbsommets, &nbarcs);

  affgraph(alpha, beta, nbsommets, nbarcs);

  supp_arc(&alpha, &beta, 0, 1, nbsommets, &nbarcs);

  affgraph(alpha, beta, nbsommets, nbarcs);

  free(alpha);
  free(beta);
}