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

#define N 10

/*--------------------------------------------------*/
/* Implémentation d'une structure de graphe orienté */
/*--------------------------------------------------*/

/* Un graphe orienté est représenté ici par sa table de listes de
   sucesseurs. De plus les sommets sont assimilés aux entiers de
   [0..nb_sommets] et on suppose que le nombre de sommets ne dépasse
   pas la constante N. Aussi on peut se permettre de stocker les
   listes de successeurs dans des tableaux d'entiers de taille N. On
   utilise alors la valeur spéciale -1 pour indiquer la fin de la
   liste dans la représentation par tableaux. Par exemple le tableau
   {0, 3, 2, -1, -1, -1, ...} représente la liste [0; 3; 2].

   La table de listes d'adjacence est alors un tableau de taille au
   plus N de telles listes.

   On peut donc représenter un graphe par un entier nb_sommets
   indiquant le nombre de ses sommets et une matrice de taille NxN
   dont les nb_sommets premières lignes représentent des listes
   d'adjacence des nb_sommets du graphe. Le contenu des lignes
   suivantes n'est pas spécifié.
*/

typedef struct {
  int nb_sommets    ;
  int adj_list[N][N];
} graphe;

graphe g0 = {
  .nb_sommets = 6,
  .adj_list = {
    { 1,  2,  3, -1, -1, -1, -1, -1, -1, -1}, /* 0 */
    { 4, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 1 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 2 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 3 */
    { 5, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 4 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 5 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 6 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 7 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 8 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 9 */
  }
};

graphe g1 = {
  .nb_sommets = 6,
  .adj_list = {
    { 1,  2,  3, -1, -1, -1, -1, -1, -1, -1}, /* 0 */
    { 4, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 1 */
    { 3,  4, -1, -1, -1, -1, -1, -1, -1, -1}, /* 2 */
    { 5, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 3 */
    { 5, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 4 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 5 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 6 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 7 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 8 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 9 */
  }
};

graphe g2 = {
  .nb_sommets = 6,
  .adj_list = {
    { 1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 0 */
    { 2,  4, -1, -1, -1, -1, -1, -1, -1, -1}, /* 1 */
    { 3, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 2 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 3 */
    { 0, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 4 */
    { 3, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 5 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 6 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 7 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 8 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 9 */
  }
};

graphe g3 = {
  .nb_sommets = 8,
  .adj_list = {
    { 1,  4, -1, -1, -1, -1, -1, -1, -1, -1}, /* 0 */
    { 5,  6, -1, -1, -1, -1, -1, -1, -1, -1}, /* 1 */
    { 1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 2 */
    { 0, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 3 */
    { 3,  5, -1, -1, -1, -1, -1, -1, -1, -1}, /* 4 */
    { 6, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 5 */
    { 2,  7, -1, -1, -1, -1, -1, -1, -1, -1}, /* 6 */
    { 2, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 7 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 8 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 9 */
  }
};

graphe g4 = {
  .nb_sommets = 6,
  .adj_list = {
    { 5, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 0 */
    { 0,  2, -1, -1, -1, -1, -1, -1, -1, -1}, /* 1 */
    { 3, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 2 */
    { 1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 3 */
    { 0,  3, -1, -1, -1, -1, -1, -1, -1, -1}, /* 4 */
    { 4, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 5 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 6 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 7 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 8 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 9 */
  }
};

graphe g6 = {
  .nb_sommets = 6,
  .adj_list = {
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 0 */
    { 0,  2, -1, -1, -1, -1, -1, -1, -1, -1}, /* 1 */
    { 1,  3, -1, -1, -1, -1, -1, -1, -1, -1}, /* 2 */
    { 4, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 3 */
    { 2, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 4 */
    { 3, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 5 */
    { 4,  7, -1, -1, -1, -1, -1, -1, -1, -1}, /* 6 */
    { 5,  6, -1, -1, -1, -1, -1, -1, -1, -1}, /* 7 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 8 */
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, /* 9 */
  }
};

/*----------------------------------------*/
/* Implémentation d'une structure de pile */
/*----------------------------------------*/

/* On propose ici une implémentation par tableau qui ne permet que de
   manipuler des piles contenant au plus N éléments.
*/
struct pile_ {
  int*   tab;
  int cursor;
} ;
typedef struct pile_*  pile ;

pile pile_create() {
  //crée une pile vide et la retourne
  //Attention contient un malloc -> libérer la mémoire après usage
  int* t = malloc(N * sizeof(int));
  pile p = malloc(sizeof(struct pile_));
  p->tab = t;
  p->cursor = 0;
  return p;
}

void empile(pile p, int n) {
  // ajoute l'entier n au sommet de la pile p
  p->tab[p->cursor] = n;
  p->cursor = p->cursor + 1;
}


bool pile_est_vide(pile p) {
  // teste si p est vide
  return (p->cursor == 0);
}

int depile(pile p) {
  //supprime le sommet de la pile p et le retourne
  p->cursor = p->cursor - 1;
  return p->tab[p->cursor];
}



/*----------------------------------------*/
/* Implémentation d'une structure de file */
/*----------------------------------------*/

/* On propose ici une implémentation par tableau qui ne permet que
   de manipuler des files sur lesquelles on réalise au plus N ajouts.
*/

struct file_ {
  int* tab;
  int  debut;
  int  fin;
} ;
typedef struct file_*  file ;

file file_create() {
  //crée une file vide et la retourne
  //Attention contient un malloc -> libérer la mémoire après usage
  int* t = malloc(N * sizeof(int));
  file f = malloc(sizeof(struct file_));
  f->tab = t;
  f->debut = 0;
  f->fin = 0;
  return f;
}


void enfile(file f, int n) {
  // ajoute n en queue de la file f
  f->tab[f->debut] = n;
  if (f->debut == N-1) {
    f->debut = 0;
  } else {
    f->debut ++;
  }
}

bool file_est_vide(file f) {
  //teste si f est la file vide
  return (f->fin == f->debut);
}

int defile(file p) {
  //retourne la valeur en tête de la file f
  int res = p->tab[p->fin] ;
  if (p->fin == N-1) {
    p->fin = 0;
  } else {
    p->fin ++;
  }
  return res;
}