# 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;
  }
}

/*
 * Remplit le tableau sommets_depart qui sera utilisé dans la suite du programme
 */
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;

  /*
   * On détermine si le sommet est un sommet de départ ou non en comptant
   * ses prédécesseurs. S'il n'en a aucun, c'est un sommet de départ.
   */
  for(i = 0 ; i < nombre_sommets ; i++) { /* Pour chaque colonne de la matrice d'adjacence. */
    total_predecesseurs = 0;

    for(j = 0 ; j < nombre_sommets ; j++) { /* Pour chaque ligne de la matrice d'adjacence. */
      if(matrice_incidence[j * nombre_sommets + i] == 1) /* On vérifie si jème sommet est prédécesseur du ième sommet. */
        total_predecesseurs++;                           /* Si c'est le cas, on incrémente. */
    }

    if(!total_predecesseurs) /* Le sommet n'a aucun prédécesseur. */
      sommets_depart[i] = 1; /* Le ième sommet est un sommet de départ. */
  }
}

/*
 * Calcule la présence ou l'absence de circuits dans le graphe.
 */
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 de i. */
      if(sommets_rencontres[sommet * nombre_sommets + i] == 1) /* Si le sommet a déjà été rencontré dans la branche actuelle. */
        return 1;                                              /* Il y a un circuit. */

      sommets_rencontres[sommet * nombre_sommets + i] = 1;  /* On sauve le sommet rencontré dans la matrice d'adjacence */

      if(presence_circuits(i)) return 1; /* Implémentation récursive. */

      sommets_rencontres[sommet * nombre_sommets + i] = -1; /* Si la fonction n'a jamais renvoyé 1 (code d'erreur), alors, il n'y a */
    }                                                       /* pas de circuit dans la branche, on enlève donc le sommet actuel de la */
                                                            /* liste des sommets rencontrés. */
  return 0; /* Tout s'est bien passé, il n'y a pas de circuit, 0 = code correct. */
}

/*
 * 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); /* Ouverture du fichier et remplissage de la matrice. */

  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;

  /* Détermine les sommets de départs pour les graphes déconnectés. */
  determiner_sommmets_depart();

  /*
   * Pour chaque sommet de départ du graphe, on étudie d'abord le graphe
   * pour déterminer la présence ou l'absence de circuits.
   * S'il n'y a pas de circuit, la fonction de calcul du rang est lancée.
   */
  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;
      }
    }

    fct_rang(i); /* Fonction de calcul du rang. */
  }

  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;
}