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

int *rangs, *matrice_incidence, *sommets_rencontres;
int nombre_sommets, nombre_arcs, sommet_depart;

int rec_element(int ligne, int colonne) {
  return matrice_incidence[ligne * nombre_sommets + colonne];
}

void def_element(int ligne, int colonne, int valeur) {
  matrice_incidence[ligne * nombre_sommets + colonne] = valeur;
}

/*
 * Lit le fichier et remplit les variables globales.
 */
void lire_fichier(const char *nom_fichier) {
  FILE *fichier = fopen(nom_fichier, "r");
  char tampon[101] = "";
  int i, extremite_initiale, extremite_terminale, valeur_arc;

  fscanf(fichier, "%d\n", &nombre_sommets);
  fscanf(fichier, "%d\n", &nombre_arcs);

  matrice_incidence = malloc(nombre_sommets * nombre_sommets * sizeof(int));

  // Initialisation de la matrice
  for(i = 0 ; i < nombre_sommets * nombre_sommets ; i++)
    matrice_incidence[i] = -1;

  while(1) {
    fgets(tampon, 100, fichier);

    if(!strcmp(tampon, "-1\n")) break;

    sscanf(tampon, "%d %d %d\n", &extremite_initiale, &extremite_terminale, &valeur_arc);
    def_element(extremite_initiale, extremite_terminale, 1);
  }
}

/*
 * Effectue un parcours en largeur pour v�rifier l'absence de circuit.
 */
int presence_circuits(int sommet) {
  /*
  struct Arc a;
  int i;

  for(i = 0 ; i < nombre_sommets ; i++)
    if(rec_element(sommet, i) == 1) { // Pour chacun des successeurs.
      a.d = sommet;
      a.a = i;

      if(trouver_element(a)) return 1;

      empiler(a);

      if(presence_circuits(i)) return 1;

      depiler();
    }

  return 0;
  */
  int i;

  for(i = 0 ; i < nombre_sommets ; i++)
    if(rec_element(sommet, i) == 1) { // Pour chacun des successeurs.
      if(sommets_rencontres[sommet * nombre_sommets + i] == 1) return 1;

      sommets_rencontres[sommet * nombre_sommets + i] = 1;

      if(presence_circuits(i)) return 1;

      sommets_rencontres[sommet * nombre_sommets + i] = -1;
    }

    printf("Le rang du sommet %d est %d.\n", sommet, fct_rang(sommet));

  return 0;
}

/*
 * Calcule le rang de chaque sommet.
 */
int fct_rang(int sommet) {
  int i, max = -1;

  if(rangs[sommet] > -1)
    return rangs[sommet];

  if(sommet == sommet_depart) {
    rangs[sommet] = 0;
    return 0;
  }

  for(i = 0 ; i < nombre_sommets ; i++) // Pour chaque sommet
    if(rec_element(i, sommet) == 1 // Si le sommet actuel est un pr�d�cesseur
       && max < fct_rang(i))
      max = fct_rang(i);

  rangs[sommet] = max + 1;

  return rangs[sommet];
}

int main(void) {
  int i;
  char nom_fichier[20];

  printf("Calcul du rang\nGraphe : ");
  scanf("%s", nom_fichier);
  printf("Sommet de d�part : ");
  scanf("%d", &sommet_depart);

  lire_fichier(nom_fichier);

  sommets_rencontres = malloc(nombre_sommets * nombre_sommets * sizeof(int));
  for(i = 0 ; i < nombre_sommets * nombre_sommets ; i++)
    sommets_rencontres[i] = -1;

  rangs = malloc(nombre_sommets * sizeof(int));
  for(i = 0 ; i < nombre_sommets ; i++)
    rangs[i] = -1;

  if(presence_circuits(sommet_depart)) {
    printf("Le graphe contient des circuits.\n");

    // Lib�rations.
    if(sommets_rencontres) free(sommets_rencontres);
    if(matrice_incidence)  free(matrice_incidence);

    return EXIT_FAILURE;
  }

/*
  for(i = 0 ; i < nombre_sommets ; i++)
    printf("Le rang du sommet %d est %d.\n", i, fct_rang(i));
  */

  // Lib�rations.
  if(sommets_rencontres) free(sommets_rencontres);
  if(rangs)              free(rangs);
  if(matrice_incidence)  free(matrice_incidence);

  return EXIT_SUCCESS;
}