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

int *rangs, *matrice_incidence, *sommets_rencontres, *sommets_depart;
int nombre_sommets;

/*
 * 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, nombre_arcs;

  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;

  for(i = 0 ; i < nombre_arcs ; i++) {
    fgets(tampon, 100, fichier);

    sscanf(tampon, "%d %d\n", &extremite_initiale, &extremite_terminale);

    matrice_incidence[extremite_initiale * nombre_sommets + extremite_terminale] = 1;
  }
}

void determiner_sommmets_depart() {
  int i, j, total_predecesseurs;

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

  for(i = 0 ; i < nombre_sommets ; i++) {
    total_predecesseurs = 0;

    for(j = 0 ; j < nombre_sommets ; j++) {
      if(matrice_incidence[j * nombre_sommets + i] == 1)
        total_predecesseurs++;
    }

    if(!total_predecesseurs)
      sommets_depart[i] = 1;
  }
}

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

  for(i = 0 ; i < nombre_sommets ; i++)
    if(matrice_incidence[sommet * nombre_sommets + 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;
    }

  return 0;
}

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

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

  for(i = 0 ; i < nombre_sommets ; i++) /* Pour chaque sommet */
    if(matrice_incidence[i * nombre_sommets + 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);

  lire_fichier(nom_fichier);

  printf("\n");

  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;

  determiner_sommmets_depart();

  for(i = 0 ; i < nombre_sommets ; i++) {
    if(sommets_depart[i] == 1) { /* Si le sommet est un sommet de départ. */
      if(presence_circuits(i)) { /* Si le graphe actuel contient des circuits. */
        printf("Le graphe contient des circuits.\n");

        break;
/*
        if(sommets_rencontres) free(sommets_rencontres);
        if(rangs)              free(rangs);
        if(matrice_incidence)  free(matrice_incidence);
      
        return EXIT_FAILURE;
*/
      }

/*      fct_rang(i); */
    }

    fct_rang(i);
  }

  for(i = 0 ; i < nombre_sommets ; i++)
    if(rangs[i] != -1)
      printf("Le rang de %d est %d.\n", i, rangs[i]);

  /* Libérations. */
  if(sommets_depart)     free(sommets_depart);
  if(sommets_rencontres) free(sommets_rencontres);
  if(rangs)              free(rangs);
  if(matrice_incidence)  free(matrice_incidence);

  return EXIT_SUCCESS;
}