Corrigé X-ENS 2026 Informatique B MP-PC-PSI — Partie I (Q1 à Q7) : Détection de cycles par parcours en profondeur

$G$ est un graphe orienté dont les arcs sont étiquetés par des entiers ; on suppose : (A0) les arcs sortants d'un sommet portent les étiquettes $0,1,2,\dots$ consécutives ; (A1) $G$ est acyclique. En Python, G est un dictionnaire global : à chaque sommet, la liste de ses successeurs, l'étiquette d'un arc étant son indice dans la liste. Certaines fonctions ajoutent des arcs ; A1 est maintenu en toute circonstance. Les opérations élémentaires sur listes et dictionnaires coûtent $O(1)$. Exemple (figure 1 du sujet) :

G = {'a': ['c', 'd'], 'b': ['d', 'c'], 'c': ['X', 'Y'], 'd': ['Y', 'X'],
     'e': ['W', 'Z'], 'W': ['Z'], 'X': [], 'Y': [], 'Z': []}

On note $s⇝t$ l'existence d'un chemin de $s$ vers $t$. Variables globales : dictionnaires époque, sortie (un entier par sommet), entiers présent, compteur. Invariants, vrais hors de l'exécution de pp : (A2) $\text{eˊpoque}[s]⩽\text{preˊsent}$ pour tout $s$ ; (A3) $\text{eˊpoque}[s]⩽\text{eˊpoque}[t]$ pour tout arc $s\to t$ ; (A4) $\text{eˊpoque}[s]=\text{eˊpoque}[t]\Rightarrow \text{sortie}[s]⩾\text{sortie}[t]$ pour tout arc $s\to t$. Code du sujet (figures 2 et 3) :

def pp(s):
    global compteur    # époque, sortie et présent sont implicitement globales
    époque[s] = présent
    for t in G[s]:
        if époque[t] != présent:
            pp(t)
    sortie[s] = compteur
    compteur += 1

def accessible(s, t):
    global présent, compteur
    if (époque[s] > époque[t] or
            (époque[s] == époque[t] and sortie[s] < sortie[t])):
        return False
    présent += 1
    pp(s)
    return époque[t] == présent

def lier(u, s):
    if not accessible(s, u):
        G[u].append(s)
        return True
    return False

Q1. Sur la figure 1, état de sortie et époque après :

for s in G.keys():
    sortie[s] = 0
    époque[s] = 0
compteur = 0
présent = 1
pp('a')

Q2. Après présent += 1 (hors de pp), montrer que $\text{eˊpoque}[t]\ne \text{preˊsent}$ pour tout $t$.
Q3. Après présent += 1 puis pp(s), montrer, pour $t\ne s$ : $s⇝t⟺\text{eˊpoque}[t]=\text{preˊsent}$.
Q4. Pour un arc $u\to v$ avec $s⇝u$, montrer qu'après pp(s), $\text{sortie}[u]⩾\text{sortie}[v]$.
Q5. Montrer qu'accessible(s, t) renvoie True si et seulement si $s⇝t$.
Q6. Montrer qu'accessible(s, t) préserve A2, A3 et A4.
Q7. Montrer que lier(u, s) préserve A1, A2, A3 et A4.