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

struct graph_s {
  // Nombre de sommets
  int n;
  // Degré de chaque somment
  int degre[100];
  // Listes d'adjacences (tableau de tableaux)
  int voisins[100][10];
  // Listes des poids des arcs
  int poids[100][10];
};

typedef struct graph_s graph;

void mise_a_jour(struct graph_s g, int u, int v, int* d){
   
    // À compléter
}
int* creer_tableau_distances(struct graph_s g, int s){
    // À compléter
    return NULL;
}

//cette fonction effectue un parcours en profondeur du graphe g depuis un sommet s et enregistre les sommets parcourus par ordre decroissant de fin de traitement dans le tableau liste.
void parcours_prof_rec(graph g,int s, bool vu[100], int liste[100], int* indice){
    if (!vu[s]){
        vu[s]=true;
        for (int i=0;i<g.degre[s];i++){
            parcours_prof_rec(g,g.voisins[s][i],vu,liste,indice);
            
        }
        liste[*indice]=s;
        (*indice)--;
        
    }
    
}

void tri_topologique(graph g, bool vu[100],int liste[100]){
    // À compléter
    for (int i = 0; i<g.n;i++){
        if (!vu[i]){
            // À compléter
        }
    }
    // À compléter
}

int* plus_court_chemin(graph g, int s){
    // À compléter
    return NULL;
}

int main(void) {

  graph g_exemple = {
    .n = 9,
    .degre = {0, 2, 1, 2, 2, 3, 1, 1, 0},
    .voisins = {
    /* 0 */ {-1}, // Degré 0 : valeur ignorée
    /* 1 */ {0, 4},
    /* 2 */ {4},
    /* 3 */ {0, 4},
    /* 4 */ {6, 7},
    /* 5 */ {2, 4, 8},
    /* 6 */ {7},
    /* 7 */ {8},
    /* 8 */ {-1} // Degré 0 : valeur ignorée
    },
    .poids = {
          {-1},
          {2,3},
          {5},
          {1,6},
          {8,2},
          {1,2,1},
          {4},
          {3},
          {-1}
      }
  };
    
    
    int liste[100] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
    
    bool vu[100] = {false,false,false,false,false,false,false,false,false,false};
    tri_topologique(g_exemple,vu,liste);

  graph* g = &g_exemple;

 

  for (int s = 0; s < g->n; s += 1) {
    printf( "%d" , liste[s]);
  }

  printf("\n");
  int* d = plus_court_chemin(g_exemple,4);
  for (int s = 0; s < g->n; s += 1) {
    //printf("(%d)\n", d[s]);
  }
    d = plus_court_chemin(g_exemple,1);
    for (int s = 0; s < g->n; s += 1) {
      //printf("(%d)\n", d[s]);
    }
    free(d);

}