Dwarfs Standing On The Shoulders Of Giants

• Le nombre de relations d’influences, un entier inférieur à 10000
• Un influenceur, un entier
• Un influencé, un entier

• Un entier qui représente la plus grande chaîne d’influence

Nous allons reprendre le fonctionnement des listes chaînées pour pouvoir connaître pour chaque noeud :

• La valeur du noeud
• La valeur du noeud qui le précède
• L’adresse du noeud suivant

Nous allons ensuite stocker chaque noeud dans un tableau contenant tous les noeuds

Pour chaque noeud du tableau nous regarderons le noeud qui le suit (dans le graphe) jusqu’à ce que l’adresse du noeud suivant n’existe pas, nous stockerons la taille du parcours et passons au noeud suivant, dans le tableau.

Nous récupérons la valeur de parcours maximale

Nous commençons par stocker toutes les valeurs rentrées dans les noeuds du tableau de noeuds :

• L’influenceur prend la valeur du noeud qui précède
• L’influencé prend la valeur du noeud actuel
• L’adresse du noeud suivant est nulle.

Nous parcourons ensuite tous les noeuds du tableau :

• Nous regardons si le noeud actuel porte la valeur d’un noeud qui précède un autre noeud dans le tableau (i.e si le noeud actuel précède un autre)

  Dans ce cas, nous assignons l’adresse du noeud précédé par le noeud actuel dans l’adresse du noeud qui suit le noeud actuel, sinon, cette adresse reste nulle.

Nous parcourons ensuite une nouvelle fois tous les noeuds du tableau :

• Chaque noeud est associé à une case dans un tableau qui contient toutes les longueurs de chaînes.

• La case associée au noeud prend la valeur de 1 plus la valeur retournée par une fonction de calcul de longueur de chaîne avec le noeud actuel

  La fonction est une fonction récursive dont le principe est le suivant :

  • Si l’adresse du noeud suivant est nulle, renvoyer 1
  • Sinon nous renvoyons 1 plus la valeur renvoyée par la fonction de calcul de longueur de chaîne avec le noeud suivant, récupéré dans l’adresse du noeud suivant.
• Si la valeur de la case est la plus grande du tableau jusqu’à la case actuelle, elle devient la longueur de chaîne maximum

Lorsque toutes les cases du tableau de longueurs sont remplies, la longueur maximum est donc la plus grande longueur de chaîne de tous les noeuds, c’est donc cette valeur que nous renvoyons.

Nous commençons par créer la structure noeud :

struct node {
    int value;
    int prev;
    node_t *next;
};

• value est la valeur du noeud
• prev est la valeur du noeud précédent
• next est l’adresse du noeud suivant, elle contient donc le noeud suivant dans le graphe

Nous créons ensuite la fonction récursive search, qui prend en argument un neoud et renvoie un entier :

int search(node_t node) {
    if(node.next == NULL){
        return 1;
    }
    else {
        return 1 + search(*node.next);
    }
}

• Si la valeur de l’adresse du noeud qui suit est nul, nous renvoyons 1, puisque un noeud seul aura une longueur de chaîne de 1
• Sinon, nous renvoyons 1 plus la valeur renvoyée par search sur le noeud suivant.

Dans la fonction principale, nous déclarons un premier tableau de noeuds, nodes :

node_t *nodes = NULL;

nodes = malloc(n*sizeof(node_t));

Ici, n est le nombres de relations d’influence

Nous créons un tableau de taille dynamique afin d’avoir un tableau de la bonne taille.

Nous créons ensuite un deuxième tableau d’entier, outputs :

int *outputs = NULL;

outputs = malloc(n*sizeof(int));

Il possède la même taille que le tableau précédent.

Avant de continuer, nous vérifions si l’allocation dynamique a bien marché pour éviter de manipuler de la mémoire qui ne nous a pas été allouée

if(nodes == NULL || outputs== NULL) {
    exit(1);
}

Ensuite, pour chaque relation d’influence rentrée :

for (int i = 0; i < n; i++) {
    int x;
    int y;
    scanf("%d%d", &x, &y);
    nodes[i].value = y;
    nodes[i].prev = x;
    nodes[i].next = NULL;
}

• Le noeud numéro i du tableau prend comme valeur la valeur y, la valeur influencée, et x, la valeur influenceuse comme valeur suivante
• L’adresse du noeud suivante commence par être initialisée à NULL, donc inexistante.

Nous entrons ensuite dans une boucle qui va regarder pour chaque noeud si un noeud le suit dans le graphe :

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){

Ainsi, pour chaque noeud, nous parcourons le tableau de noeuds.

Pour savoir si un noeud suit un autre dans le graphe, nous regardons si la valeur d’un noeud et la valeur du noeud qui précède un autre noeud sont les mêmes :

if(nodes[i].value == nodes[j].prev){
    nodes[i].next = &nodes[j];
}

Avant de continuer, nous initialisons la longueur de chaîne maximum, max, à 1, car un noeud seul possède une longueur de chaîne de 1

int max = 1;

Pour chaque neoud du tableau :

for(int i = 0; i < n; i++){
    outputs[i] = 1 + (search(nodes[i]));
    max = outputs[i]>max?outputs[i]:max;
}

• Nous passons le noeud dans la fonction search et la case correspondante dans le tableau outputs prend la valeur 1 plus la valeur renvoyée par la fonction

• Si la valeur renvoyée est plus grande que max, max prend comme valeur la valeur renvoyée.

Nous renvoyons ensuite la longueur de chaîne maximum, qui est la valeur de max

printf("%d\n",max);

Nous libérons enfin les tableaux nodes et outputs :

free(nodes);
free(outputs);
nodes = NULL;
outputs = NULL;
return 0;

Lien vers la documentation doxygen