#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){
    if (d[u]+g.poids[u][v]<d[g.voisins[u][v]]){
        d[g.voisins[u][v]]=d[u]+g.poids[u][v];
    }
}
int* creer_tableau_distances(struct graph_s g, int s){
    int* res = malloc(g.n*sizeof(int));
    for (int i = 0 ; i<g.n;i++){
        res[i]=100000;
    }
    res[s]=0;
    return res;
}
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]){
    int* indice = malloc(sizeof(int));
    *indice=g.n-1;
    for (int i = 0; i<g.n;i++){
        if (!vu[i]){
            parcours_prof_rec(g,i,vu,liste,indice);
        }
    }
    free(indice);
}

int* plus_court_chemin(graph g, int s){
    int* d = creer_tableau_distances(g,s);
    int liste[100];
    bool vu[100];
    tri_topologique(g,vu,liste);
    for (int x = 0; x<g.n;x++){
        for(int voisin = 0; voisin < g.degre[liste[x]];voisin++){
            mise_a_jour(g,liste[x],voisin,d);
        }
    }
    return d;
}

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}
      }
  };
    
    printf(" %d", g_exemple.poids[4][0]);
    
    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);

  //bool pairs[9] = {true, false, true, false, true, false, true, false, true};

  graph* g = &g_exemple;

  //printf("Le degré maximal d'un sommet pair de g est : %d\n\n", degre_max(g, pairs));

  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]);
  }
    free(d);

}