Corrigé Mines-Ponts 2025 Informatique II MPI — Section 1.1 (Q1 à Q11) : Le jeu de Shannon en C : listes d'adjacence et unir & trouver

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique II MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un graphe non orienté connexe $G = (V, E)$ à $n$ sommets numérotés de $0$ à $n - 1$ est fixé, avec deux sommets distingués $s = 0$ et $t = 1$ . Deux joueurs, Positus et Minus, marquent à tour de rôle une arête non encore marquée. Positus gagne si les arêtes qu'il a marquées relient $s$ à $t$ par un chemin ; Minus gagne si toutes les arêtes sont marquées sans que ce soit le cas. On note $M \subseteq E$ l'ensemble des arêtes marquées et $M^{+} \subseteq M$ celles de Positus. Code fourni par le sujet :


#define s 0
#define t 1

struct link {
    int node;
    struct link * next;
};
typedef struct link link_t;

struct game {
    int n;             // Nombre de sommets
    int nm;            // Nombre d'aretes non marquees
    link_t ** adj_arr; // Voisins non marques
    int * cmps;        // Composantes connexes creees par Positus
};
typedef struct game game_t;

game_t gm;

La variable globale gm est le jeu en cours : gm.adj_arr[u] pointe vers la liste chaînée des voisins de $u$ dans le graphe $(V, E ∖ M)$ des arêtes encore jouables (les arêtes marquées disparaissent de gm) ; gm.cmps code, en « unir & trouver », les composantes connexes de $(V, M^{+})$ .

Unir & trouver. Un tableau $A$ de taille $n$ code une forêt orientée vers les racines : $A [u] = u$ si $u$ est une racine, appelée identifiant de sa classe, et $A [u]$ est le parent de $u$ sinon.

Q1. void gm_init(int n) : jeu sur $n$ sommets sans arête, gm.cmps valant $0, 1, \dots, n - 1$ .
Q2. void gm_addedge(int u, int v) : ajouter l'arête ${u, v}$ , codée par les deux arcs $(u, v)$ et $(v, u)$ .
Q3. bool gm_remove(int u, int v) : retirer l'arête ${u, v}$ ; true si la suppression a eu lieu.
Q4. int uf_find(int n, int * A, int u) : identifiant de la classe de $u$ , sans modifier $A$ .
Q5. bool uf_unite(int n, int * A, int u, int v) : réunir les classes de $u$ et $v$ ; true si $A$ a changé.
Q6. int gm_find(int u) : identifiant de la composante de $u$ dans $(V, M^{+})$ .
Q7. void gm_unite(int u, int v) : réunir les composantes de $u$ et $v$ .
Q8. bool has_P_won(void) : le jeu est-il gagné par Positus ?
Q9. bool has_P_lost(void) : le jeu est-il perdu par Positus ?
Q10. void play_P(int u, int v) : Positus joue ${u, v}$ ; une assertion refuse un coup illicite.
Q11. void play_M(int u, int v) : même chose pour Minus.

Corrigé

Tous les programmes de cette partie ont été compilés ensemble (gcc -Wall -Wextra -std=c99, sans avertissement) et exécutés : initialisation, ajout des six arêtes de $K_{4}$ , suppressions en tête, au milieu, en fin de liste et d'une arête absente, partie complète sur $K_{4}$ gagnée par Positus, partie sur le chemin $s$ – $a$ – $t$ perdue par Positus, sommet de degré $200$ dont on retire les arêtes dans le désordre ; l'outil leaks ne signale aucune fuite. Les en-têtes stdlib.h, stdbool.h, assert.h sont supposés inclus.

Q1. La variable gm est globale : elle existe déjà, on ne l'alloue pas. On alloue en revanche ses deux tableaux, puis on remplit les quatre champs.


void gm_init(int n) {
    gm.n = n;
    gm.nm = 0;
    gm.adj_arr = malloc(n * sizeof(link_t *));
    gm.cmps = malloc(n * sizeof(int));
    assert(gm.adj_arr != NULL && gm.cmps != NULL);
    for (int u = 0; u < n; u++) {
        gm.adj_arr[u] = NULL;   /* aucune arete : toutes les listes sont vides */
        gm.cmps[u] = u;         /* chaque sommet est seul dans sa classe */
    }
}

adj_arr est un tableau de pointeurs de maillons, d'où sizeof(link_t *). Avec $M^{+} = \emptyset$ , les composantes de $(V, M^{+})$ sont les singletons : chaque sommet est sa propre racine, ce qu'exprime gm.cmps[u] = u. Coût $O (n)$ . gm n'étant pas un pointeur, on accède à ses champs par un point (gm.n), et non par une flèche.

Q2. On ajoute un maillon en tête de chacune des deux listes (aucune recherche n'est nécessaire), à l'aide d'une fonction auxiliaire qui insère v en tête de la liste de u :


void push_front(int u, int v) {
    link_t * l = malloc(sizeof(link_t));
    assert(l != NULL);
    l->node = v;
    l->next = gm.adj_arr[u];   /* on raccroche l'ancienne tete */
    gm.adj_arr[u] = l;
}

void gm_addedge(int u, int v) {
    push_front(u, v);   /* arc (u, v) */
    push_front(v, u);   /* arc (v, u) */
    gm.nm++;            /* une arete jouable de plus */
}

Coût $O (1)$ . Le maillon est alloué dans le tas par malloc : un maillon local disparaîtrait au retour de la fonction. On ne vérifie pas que l'arête est absente, ce que le sujet ne demande pas.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →